首页 > 代码库 > 51nod1586 约数和

51nod1586 约数和

2024-08-13 15:53:59   219人阅读

果然我自己写的读入优化naive！。。。换题目给的读入优化就A了。。。话说用visual交快了好多啊。。。

const int BufferSize=1<<16;char buffer[BufferSize],*head,*tail;inline char Getchar() {    if(head==tail) {        int l=fread(buffer,1,BufferSize,stdin);        tail=(head=buffer)+l;    }    return *head++;}inline int read() {    int x=0,f=1;char c=Getchar();    for(;!isdigit(c);c=Getchar()) if(c==‘-‘) f=-1;    for(;isdigit(c);c=Getchar()) x=x*10+c-‘0‘;    return x*f;}
#include<cstdio>#include<cstring>#include<cctype>#include<algorithm>using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)#define dwn(i,s,t) for(int i=s;i>=t;i--)#define clr(x,c) memset(x,c,sizeof(x))#define ll long longconst int BufferSize=1<<14;char buffer[BufferSize],*head,*tail;inline char Getchar() {    if(head==tail) {        int l=fread(buffer,1,BufferSize,stdin);        tail=(head=buffer)+l;    }    return *head++;}inline int read() {    int x=0,f=1;char c=Getchar();    for(;!isdigit(c);c=Getchar()) if(c==‘-‘) f=-1;    for(;isdigit(c);c=Getchar()) x=x*10+c-‘0‘;    return x*f;}const int nmax=1e6+5;ll c[nmax];int t[nmax];int main(){	int n=read(),m=read(),u,v,d;	rep(i,1,n) for(int j=i;j<=n;j+=i) ++t[j];	rep(i,1,m){		u=read();		if(u==1){			v=read(),d=read();			for(int j=v,k=1;j<=n;j+=v,++k) c[j]+=d*t[k];		}else{			v=read();printf("%lld\n",c[v]);		}	}	return 0;}

　　

1586 约数和技术分享
基准时间限制：2 秒 空间限制：131072 KB 分值: 80 难度：5级算法题
技术分享 收藏
技术分享 关注

有三个下标从1到n的数组a、b、c。

a数组初始全为0。

 b[i]=∑j|ia[j] 

 c[i]=∑j|ib[j] 

需要进行下列操作：

1 x y :将a[x]加上y

2 x :询问当前c[x]的值

 
j | i 表示j是i的约数。
由于数据比较多，请用输入挂。
以下供参考。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
Input
第一行两个整数，n和q，分别表示数组下标范围和操作次数。（1<=n,q<=1,000,000）接下来q行，描述一个操作。(x随机,1<=x<=n,1<=y<=10^6)
Output
对于每一个第二种操作输出一个答案。
Input示例
5 51 2 42 22 41 1 32 5
Output示例
486

51nod1586 约数和


联系
我们