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

1. 禁快递 关饭店，关西湖，关菜场还不够，我看得把汽车也禁止了，要是发生车祸多不好，没有事故大家都欣慰不是？最好把人都运出城，用电网包起来，没有事故大家都欣慰的嘛。

2. @无心长住, ispring的软件，好像只要包含视频，音频文件，一般情况下都转换不成功。。。这个不好办了，可以试试其他的工具如用Camtasia Studio录制PPT。

3. @无心长住, ispring的软件，好像只要包含视频，音频文件，一般情况下都转换不成功。。。这个不好办了，可以试试其他的工具如用Camtasia Studio录制PPT。

4. @无心长住, ispring的软件，好像只要包含视频，音频文件，一般情况下都转换不成功。。。这个不好办了，可以试试其他的工具如用Camtasia Studio录制PPT。

5. @无心长住, ispring的软件，好像只要包含视频，音频文件，一般情况下都转换不成功。。。这个不好办了，可以试试其他的工具如用Camtasia Studio录制PPT。

6. @无心长住, ispring的软件，好像只要包含视频，音频文件，一般情况下都转换不成功。。。这个不好办了，可以试试其他的工具如用Camtasia Studio录制PPT。