題目鏈接：Click here~~
第一道容斥原理的題目。
題意：
有一個元素為 1~n 的數列{An}，有2種操作（1000次）：
1、求某段區間 [a,b] 中與 p 互質的數的和。
2、將數列中某個位置元素的值改變。
解題思路：
對於操作1，解的性質滿足區間減法，則我們只需要考慮如何求 [1,n] 中與 p 互質的數的和即可。
考慮到與 p 互質的數不太好解，於是可以通過先求出與 p 不互質的數的和，然後與總和作差得到。
而一個數 x 若與 p 不互質，當且僅當兩者素因子的集合有交集。
設 p 的素因子是{P1,P2,…,Pk}，於是與 p 不互質的數的素因子集合可以表示成 {P1} U {P2} U … U {Pk}。
那麼與 p 不互質的數的集合可以表示成 W = { P1的倍數 } U { P2的倍數 } U … U { Pk的倍數 }。
其中，{ Pk的倍數 } = { Pk*1 } + { Pk*2 } + … + { Pk*Mk } ( Pk*Mk<=n && Pk*(Mk+1)>n )。
從而，ans = sum{ W }。
於是可以通過容斥原理，求得問題的解。
舉個簡單的例子，假如 k=2，則 ans = 【sum{ P1的倍數 } + sum{ P2的倍數 } - sum{ P1*P2的倍數 }】。
其中，XX的倍數可以通過等差公式求得。
對於操作2，由於操作比較少，我們可以保存這些操作，當遇到要求和的時候，我們遍歷之前保存的操作，找到在區間中改變的值，對應修改即可。
[cpp]
#include <map>
#include <stdio.h>
typedef __int64 LL;
using namespace std;
#define N 650
bool np[N];
int prime[120],fac[9],F_top,p;
LL ans;
void get_prime()
{
int top = -1;
for(int i=2;i<N;i++)
if(!np[i])
{
prime[++top] = i;
for(int j=i+i;j<N;j+=i)
np[j] = true;
}
}
void Div(int n)
{
F_top = 0;
for(int i=0;prime[i]*prime[i]<=n;i++)
{
if(n % prime[i])
continue;
while(n % prime[i] == 0)
n /= prime[i];
fac[F_top++] = prime[i];
}
if(n != 1)
fac[F_top++] = n;
}
LL PreSum(int n)
{
return (LL)n*(n+1)/2;
}
void dfs(int i,int cnt,int m,int n,int num,int x) // C(n,m).
{
if(cnt == m)
{
LL sum = num * PreSum(x/num);
m&1 ? ans -= sum : ans += sum;
return ;
}
if(num*fac[i] <= x)
dfs(i+1,cnt+1,m,n,num*fac[i],x);
if(n-1-i >= m-cnt)
dfs(i+1,cnt,m,n,num,x);
// if(num*fac[i] > x || n-i < m-cnt)
// return ;
// dfs(i+1,cnt+1,m,n,num*fac[i],x);
// dfs(i+1,cnt,m,n,num,x);
}
LL sovle(int n)
{
ans = PreSum(n);
for(int m=1;m<=F_top;m++)
dfs(0,0,m,F_top,1,n);
return ans;
}
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
int main()
{
int z,n,Q,cmd,a,b;
get_prime();
scanf("%d",&z);
map<int,int> M;
while(z--)
{
M.clear();
scanf("%d%d",&n,&Q);
while(Q--)
{
scanf("%d",&cmd);
if(cmd == 1)
{
scanf("%d%d%d",&a,&b,&p);
Div(p);
ans = sovle(b) - sovle(a-1);
for(map<int,int>::iterator it=M.begin();it!=M.end();it++)
if((*it).first >= a && (*it).first <= b)
{
if(gcd((*it).first,p) == 1)
ans -= (*it).first;
if(gcd((*it).second,p) == 1)
ans += (*it).second;
}
printf("%I64d\n",ans);
}
else
{
scanf("%d%d",&a,&b);
M[a] = b;
}
}
}
return 0;
}
