http://acm.hdu.edu.cn/showproblem.php?pid=4407
題意：給定初始n個數1..n，兩個操作，①1 x y p 詢問第x個數到第y個數中與p互質的數的和; ②：2 x y 把第x個數變成y；
思路：
把p分解質因子，然後找出(1,pos)内與p不互質的，然後用的減去就是互質的和，第二個操作用到map映射，記錄在那個位置改變之後的數。
1 #include <cstdio>
2 #include <cstring>
3 #include <map>
4 #include <vector>
5 #include <algorithm>
6 #define LL __int64
7 #define maxn 400001
8 using namespace std;
9
10 int t;
11 int n,m;
12
13 LL gcd(LL a,LL b)
14 {
15 return b==0?a:gcd(b,a%b);
16 }
17
18
19 LL deal(LL x,LL y)
20 {
21 LL res=x*(x+1)/2;
22 vector<int>p;
23 for(int i=2; i*i<=y; i++)
24 {
25 if(y%i==0)
26 {
27 p.push_back(i);
28 while(y%i==0)
29 {
30 y/=i;
31 }
32 }
33 }
34 if(y>1) p.push_back(y);
35 LL ans=0;
36 for(int i=1; i<(1<<((int)p.size())); i++)
37 {
38 LL xx=0;
39 LL c=1;
40 for(int j=0; j<(int)p.size(); j++)
41 {
42 if(i&(1<<j))
43 {
44 xx++;
45 c*=p[j];
46 }
47 }
48 LL t=x/c;
49 LL sum=((t+1)*t/2)*c;
50 if(xx%2)
51 {
52 ans+=sum;
53 }
54 else
55 ans-=sum;
56 }
57 return res-ans;
58 }
59
60 int main()
61 {
62 map<int,int>q;
63 scanf("%d",&t);
64 while(t--)
65 {
66 q.clear();
67 scanf("%d%d",&n,&m);
68 int x,y,op,pp;
69 for(int i=1; i<=m; i++)
70 {
71 scanf("%d",&op);
72 if(op==1)
73 {
74 scanf("%d%d%d",&x,&y,&pp);
75 LL sum=deal((LL)y,(LL)pp)-deal((LL)(x-1),(LL)pp);
76 map<int,int>::iterator it=q.begin();
77 while(it!=q.end())
78 {
79 if(it->first>=x&&it->first<=y)
80 {
81 if(gcd(it->first,pp)==1)
82 {
83 sum-=it->first;
84 }
85 if(gcd(it->second,pp)==1)
86 {
87 sum+=it->second;
88 }
89 }
90 it++;
91 }
92 printf("%I64d
",sum);
93 }
94 else
95 {
96 scanf("%d%d",&x,&y);
97 q[x]=y;
98 }
99 }
100 }
101 return 0;
102 } View Code