XXX is puzzled with the question below:
1, 2, 3, …, n (1<=n<=400000) are placed in a line. There are m (1<=m<=1000) operations of two kinds.
Operation 1: among the x-th number to the y-th number (inclusive), get the sum of the numbers which are co-prime with p( 1 <=p <= 400000).
Operation 2: change the x-th number to c( 1 <=c <= 400000).
For each operation, XXX will spend a lot of time to treat it. So he wants to ask you to help him.
Input
There are several test cases.
The first line in the input is an integer indicating the number of test cases.
For each case, the first line begins with two integers — the above mentioned n and m.
Each the following m lines contains an operation.
Operation 1 is in this format: “1 x y p”.
Operation 2 is in this format: “2 x c”.
Output
For each operation 1, output a single integer in one line representing the result.
Sample Input
1
3 3
2 2 3
1 1 3 4
1 2 3 6
Sample Output
7
0
题意:一开始有1到N这N个数，有M次操作。
操作1：查询区间【L,R】内所有与P互质的数之和。
操作2：改变第X数的值为c
题解：首先思路和HDU-4135这道题基本一样，都是利用容斥原理先求出与P非互质的数，然后用R-L+1这段区间内的数来减去非互质数之和得到互质数之和。
关于求和，因为一开始这段数列是等差数列，我们可以以O(1)的复杂度求和，然后去减非互质。
首先还是求出数P的质因数。然后利用容斥原理得到区间【L,R】内所有非互质数的和。
我们已经求出了数N有cnt个质因子，对于cnt个质因子，可以单个出现，可以多个组合出现，共有2^cnt次方种选择方式，即，我们遍历2^cnt种情况，每种情况可以用一个二进制表示，如情况3即11，情况9即1001表示第一个素因子和第四个素因子组合在一起形成新的因子。这样用素因子组合得到所有因子。然后用给出的边界m除以每一个因子得到个数，根据个数判断是加上还是减掉。
这个“个数”是一个以因子为首项，长度为“个数”的等差数列，求这个等差数列的和即某些非互质数的和。在接下来的因子中，以容斥原理公式不断对等差序列的和进行加减最后可以得到1,m内所有与P非互质数的和。然后从L~R的求和中减去【1，R】-【1，L】的非互质和。即结果。
对于【L,R】这段数的和可以用
此处n=(r-l+1)
a1=L
d=1
因此为L*（R-L+1）+(R-L+1) * (R-L)/2
关于修改，因为只有1000次修改，因此我们可以直接在原序列的基础上先求出区间和后，再遍历所有被修改的位置，如在查询区间内，判断被修改后的值是否对区间和造成影响，然后直接修改初始求出的区间和。
对于修改，可以用map直接存储，因为修改我们只需要最新的，因此每个位置都存储最新的修改值即可。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL t,n,m,p,a[100080];
LL cnt=0;
map<LL,LL>vis;
map<LL,LL>::iterator it;
void prim(LL num)
{
cnt=0;
for(LL i=2;i*i<=num;i++)
{
if(num%i==0)
{
a[cnt++]=i;
while(num%i==0)num/=i;
}
}
if(num!=1)a[cnt++]=num;
}
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
LL all(LL m)
{
LL ans=0;///非互质数之和
for(LL i=1; i<(1<<cnt); i++)
{
LL sum=1,num1=0,tmp=i;
for(LL j=0; j<cnt; j++)
{
if(1&tmp)
{
sum*=a[j];
num1++;
}
tmp>>=1;
}
tmp=m/sum;
if(num1&1) ans+=tmp*(tmp+1)*sum/2;
else ans-=tmp*(tmp+1)*sum/2;
}
return ans;
}
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
vis.clear();
while(m--)
{
LL com,x,y;
LL ans=0;
scanf("%lld",&com);
if(com==1)
{
scanf("%lld%lld%lld",&x,&y,&p);
prim(p);
ans=x*(y-x+1)+(y-x+1)*(y-x)/2;
// printf("----%lld %lld %lld
",ans,all(y),all(x-1));
ans-=all(y)-all(x-1);
for(it=vis.begin(); it!=vis.end(); it++)
{
if(it->first>=x&&it->first<=y)
{
if(gcd(it->first,p)==1)ans-=it->first;
if(gcd(it->second,p)==1)ans+=it->second;
}
}
printf("%lld
",ans);
}
else
{
scanf("%lld%lld",&x,&p);
vis[x]=p;
}
}
}
}
/*
99
3 99
1 3 3 7
2 2 3
1 3 3 7
*/