hdu4947 GCD Array

hdu4947 GCD Array

​​ Problem Description Teacher Mai finds that many problems about arithmetic function can be reduced to the following problem:

Maintain an array a with index from 1 to l. There are two kinds of operations:

Add v to ax for every x that gcd(x,n)=d.Query

Input There are multiple test cases, terminated by a line “0 0”.

For each test case, the first line contains two integers l,Q(1<=l,Q<=5*10^4), indicating the length of the array and the number of the operations.

In following Q lines, each line indicates an operation, and the format is “1 n d v” or “2 x” (1<=n,d,v<=2*10^5,1<=x<=l).

Output For each case, output “Case #k:” first, where k is the case number counting from 1.

Then output the answer to each query.

Sample Input 6 4 1 4 1 2 2 5 1 3 3 3 2 3 0 0

Sample Output Case #1: 6 7

Author xudyh

Source 2014 Multi-University Training Contest 8

Recommend We have carefully selected several similar problems for you: 6297 6296 6295 6294 6293 考虑定义ai=∑d|inf(d) a i = ∑ d | i n f ( d ) 那么考虑题意中一个v需要加到哪几个ai a i 上 在原式中：ax+=v×[gcd(x,n)=d]=v×[gcd(x/d,n/d)=1] a x + = v × [ g c d ( x , n ) = d ] = v × [ g c d ( x / d , n / d ) = 1 ] 然后可以套路反演一下ax+=v×∑p|nd,p|xdμ(p) a x + = v × ∑ p | n d , p | x d μ ( p ) 那么我们发现枚举nd n d 的所有约数的d倍就是我这次添加操作会影响的关于ax a x 的那些f数组的位置 所以添加f(pd)+=v∗μ(p) f ( p d ) + = v ∗ μ ( p ) 我们询问一个点a[x]=∑d|xf(d) a [ x ] = ∑ d | x f ( d ) ∑i=1x∑d|if(d) ∑ i = 1 x ∑ d | i f ( d ) 可以枚举d ∑d=1xxdf(d) ∑ d = 1 x x d f ( d ) 针对xd x d 数论分块即可 然后树状数组求前缀和 查询的时候树状数组求和即可

#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=2e5+10;int n,q,prime[N],tot,mu[N];ll s[N];vector fac[N];bool not_prime[N];inline void init(){ mu[1]=1; for (int i=2;i<=2e5;++i){ if(!not_prime[i]) prime[++tot]=i,mu[i]=-1; for (int j=1;prime[j]*i<=2e5;++j){ not_prime[prime[j]*i]=1; if (i%prime[j]==0){ mu[prime[j]*i]=0;break; }else mu[prime[j]*i]=-mu[i]; } } for (int i=1;i<=2e5;++i) for (int j=i;j<=2e5;j+=i) fac[j].push_back(i);}inline void add(int x,int v){ while(x<=2e5) s[x]+=v,x+=x&-x;}inline ll query(int x){ static ll tmp;tmp=0; while(x) tmp+=s[x],x-=x&-x;return tmp;}int main(){ freopen("hdu4947.in","r",stdin); int cnt=0;init(); while(1){ n=read();q=read();if(!n&&!q) break; printf("Case #%d:\n",++cnt); memset(s,0,sizeof(s)); for (int owo=1;owo<=q;++owo){ int op=read(); if(op==1){ int x=read(),d=read(),v=read(); if (x%d) continue;x/=d; for (int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。