HDU 4407 Sum

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int maxn = 100;
 5 int pm[maxn],tot;
 6 unordered_map<int,int>ump;
 7 void init(LL x){
 8     tot = 0;
 9     for(int i = 2; i*i <= x; ++i){
10         if(x%i == 0){
11             pm[tot++] = i;
12             while(x%i == 0) x /= i;
13         }
14     }
15     if(x > 1) pm[tot++] = x;
16 }
17 LL solve(LL x,LL p){
18     LL ret = (x*(x + 1))>>1;
19     init(p);
20     for(int i = 1; i < (1<<tot); ++i){
21         int cnt = 0;
22         LL tmp = 1;
23         for(int j = 0; j < tot; ++j){
24             if((i>>j)&1){
25                 ++cnt;
26                 tmp *= pm[j];
27             }
28         }
29         LL y = x/tmp;
30         if(cnt&1) ret -= ((y*(y + 1))>>1)*tmp;
31         else ret += ((y*(y + 1))>>1)*tmp;
32     }
33     return ret;
34 }
35 int main(){
36     int kase,n,m,op,x,y,p;
37     scanf("%d",&kase);
38     while(kase--){
39         ump.clear();
40         scanf("%d%d",&n,&m);
41         for(int i = 0; i < m; ++i){
42             scanf("%d",&op);
43             if(op == 2){
44                 scanf("%d%d",&x,&y);
45                 ump[x] = y;
46             }else{
47                 scanf("%d%d%d",&x,&y,&p);
48                 LL ret = solve(y,p) - solve(x-1,p);
49                 for(auto &it:ump){
50                     if(it.first >= x && it.first <= y){
51                         if(__gcd(it.first,p) == 1) ret -= it.first;
52                         if(__gcd(it.second,p) == 1) ret += it.second;
53                     }
54                 }
55                 printf("%I64d\n",ret);
56             }
57         }
58     }
59     return 0;
60 }