2015
05-24

# Sum

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.

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".

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".

1
3 3
2 2 3
1 1 3 4
1 2 3 6

7
0

1、求某段区间 [a,b] 中与 p 互质的数的和。

2、将数列中某个位置元素的值改变。

#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 || 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;
}