hdu 4407 Sum(容斥) - c++编程基础

http://acm.hdu.edu.cn/showproblem.php?pid=4407

起初有n个数1~n，这里有m个操作，两种类型。操作1：求出[x,y]区间内与p互质的数的和。操作2：将第x位置的数变成y。对于每一个询问，输出结果。

因为只有1000次操作，而且起初是有序的。那么对于第i个询问，我们先忽略i之前的所有的第2种操作，即认为n个数为1~n，根据容斥原理求出[x,y]区间内与p互质的数之和，然后遍历i之前的操作2，对所求的答案进行调整即可。wa了无数次，改了好久，是因为我忽略的一点，对x位置的数有可能进行多次修改，我们只需考虑最后一次修改即可。所以可用用map保存一下操作2。

#include 
  
   
#include 
   
     #include 
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define LL __int64 //#define LL long long #define eps 1e-9 #define PI acos(-1.0) using namespace std; const int maxn = 400010; int n,m; bool flag[maxn]; int prime[maxn]; int fac[100]; int facCnt; LL ans; map
                
                 M; int gcd(int a, int b) { if(b == 0) return a; return gcd(b,a%b); } void getPrime() { memset(flag,false,sizeof(flag)); prime[0] = 0; for(int i = 2; i < maxn; i++) { if(flag[i] == false) prime[++prime[0]] = i; for(int j = 1; j <= prime[0]&&prime[j]*i < maxn; j++) { flag[prime[j]*i] = true; if(i % prime[j] == 0) break; } } } void getFac(int num) { int tmp = num; facCnt = 0; for(int i = 1; i <= prime[0]&&prime[i]*prime[i] <= tmp; i++) { if(tmp % prime[i] == 0) { fac[facCnt++] = prime[i]; while(tmp % prime[i] == 0) tmp /= prime[i]; } if(tmp == 1) break; } if(tmp > 1) fac[facCnt++] = tmp; } LL getSum(int t) { return ((1 + 1LL * t) * 1LL * t) >> 1; } //求【1，r】内与该数互质的数之和。 LL cal(int r) { LL anw = getSum(r); LL tmp = 0; for(int i = 1; i < (1<
                 
                  ::iterator it; for(it = M.begin(); it != M.end(); it++) { if(it->first >= x && it->first <= y) { if(gcd(z,it->first) == 1) ans -= it->first; if(gcd(z,it->second) == 1) ans += it->second; } } printf("%I64d\n",ans); } else { scanf("%d %d",&x,&y); M[x] = y; } } } return 0; }