HDU 4407 12年金華網絡賽H題(容斥原理)

HDU 4407 12年金華網絡賽H題(容斥原理)

題意：
有一個元素為 1~n 的數列{An}，有2種操作（1000次）：
1、求某段區間 [a,b] 中與 p 互質的數的和。
2、將數列中某個位置元素的值改變。

分析：由於最開始是從1~n的數，之後再修改的值，所以先求解當沒有發生改變的值的和求出來，求法采用容斥原理求1~n中與m互質的數的和。先對m進行素因子分解，然後找小於n中能整除m的素因子的個數，這些數求和就是那些不互質的數的和。然後再把更改的東西加加減減就好了。不過別忘判斷是不是在x，y范圍內。（數據有可能爆int）
容斥原理詳見：容斥原理；

代碼如下：

1. #include   
2. #include   
3. #include   
4. #include   
5. #include   
6. #include   
7. #include   
8. #include   
9. using namespace std;  
10. struct sa{  
11.     int fen[10];  
12.     int k;  
13. }p[400005];  
14. int a[400005];  
15. bool phi[400005];  
16. int gcd(int a,int b){  
17.     return b==0?a:gcd(b,a%b);  
18. }  
19. long long sum;  
20. void dfs(int id,int w,int k,long long m,long long sumsum){  
21.     if(id==p[k].k+1)return;  
22.     for(int i=w;i
23.         long long temp=p[k].fen[i]*sumsum;  
24.         if(id&1){  
25.             long long t=m/temp;  
26.             sum-=temp*(t+1)*t/2;  
27.         }  
28.         else {  
29.             long long t=m/temp;  
30.             sum+=temp*(t+1)*t/2;  
31.         }  
32.         dfs(id+1,i+1,k,m,temp);  
33.     }  
34. }//遞歸實現容斥原理  
35. long long solve(long long n,int pp){  
36.     sum=n*(n+1)/2;  
37. //    cout<  
38.     dfs(1,0,pp,n,1);  
39.     return sum;  
40. }  
41. int main()  
42. {  
43.     int t;  
44.     scanf("%d",&t);  
45.     for(int i=1;i<400005;i++)  
46.     p[i].k=0;  
47.     memset(phi,0,sizeof(phi));  
48.     phi[1]=true;  
49.     for(int i=2;i<400005;i++){  
50.         if(!phi[i]){  
51.             for(int j=i;j<400005;j+=i){  
52.                 phi[j]=true;  
53.                 p[j].fen[p[j].k]=i;  
54.                 p[j].k++;  
55.             }  
56.         }  
57.     }//先遞推求解素因子的和  
58.     while(t--){  
59.         map<int,int>a;  
60.         map<int,int>::iterator it;  
61.         int n,m;  
62.         scanf("%d%d",&n,&m);  
63.         while(m--){  
64.             int k;  
65.             scanf("%d",&k);  
66.             if(k==2){  
67.                 int x,c;  
68.                 scanf("%d%d",&x,&c);  
69.                 a[x]=c;  
70.             }  
71.             else if(k==1){  
72.                 int x,y,pp;  
73.                 long long ans;  
74.                 scanf("%d%d%d",&x,&y,&pp);  
75.                 ans=solve(y,pp)-solve(x-1,pp);  
76.                 for(it=a.begin();it!=a.end();it++){  
77.                     if(it->first>=x&&it->first<=y){//千萬別忘了這個條件  
78.                         if(gcd(it->first,pp)==1)  
79.                         ans-=it->first;  
80.                         if(gcd(it->second,pp)==1)  
81.                         ans+=it->second;  
82.                     }  
83.                 }  
84.                 printf("%I64d\n",ans);  
85.             }  
86.         }  
87.     }  
88.     return 0;  
89. }