这题不难吧，如果正在做组合的题。。。
使用容斥原理求解出（1~x）的与p互素的和，这是很容易的，很明显，首先要把p分解质因数。
而对于第二个操作，记录下他的转换的顺序，当要执行第一个操作时，遍历一次记录下的操作转换就可以了。
呃，这题虽然想到，但是，我的WA。看了网上的，思路和我的一样，我自己COPY别人的代码下来对拍数据，无误。。但就是过不了。能想到的边界数据也试过了，还是过不了。。求各路大神指错。
我的代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define Np 700
#define LL __int64
using namespace std;
bool isprime[Np];
LL prime[Np],np;
LL dsorp[Np],dp;
struct Update{
LL pos,val;
};
Update up[1500];
LL upp;
void initial(){
memset(isprime,true,sizeof(isprime));
np=0;
isprime[1]=false;
for(LL i=2;i<Np;i++){
if(isprime[i]){
prime[np++]=i;
for(LL j=i*i;j<Np;j+=i){
isprime[j]=false;
}
}
}
}
void dfs(LL i,LL num,LL tmp,LL &s,LL n){
if(i>=dp){
if(num==0){
s=(1+n)*n/2;
}
else{
LL sc=n/tmp;
if(num&1){
s=s-((sc+1)*sc/2*tmp);
}
else{
s=s+((sc+1)*sc/2*tmp);
}
}
return;
}
dfs(i+1,num,tmp,s,n);
dfs(i+1,num+1,tmp*dsorp[i],s,n);
}
LL work(LL x,LL y,LL p){
dp=0;
for(LL i=0;i<np&&prime[i]*prime[i]<=p;i++){
if(p%prime[i]==0){
dsorp[dp++]=prime[i];
while(p%prime[i]==0)
p=p/prime[i];
}
}
if(p>1)
dsorp[dp++]=p;
LL ansy,ansx;
ansy=ansx=0;
dfs(0,0,1,ansy,y);
dfs(0,0,1,ansx,x-1);
return ansy-ansx;
}
LL gcd(LL a,LL b){
if(b==0) return a;
return gcd(b,a%b);
}
bool coprime(LL a,LL p){
if(gcd(a,p)==1LL)
return true;
else return false;
}
int main(){
LL T,n,m,op,x,y,p,c;
initial();
scanf("%I64d",&T);
while(T--){
scanf("%I64d%I64d",&n,&m);
upp=0;
for(LL i=1;i<=m;i++){
scanf("%I64d",&op);
if(op==1LL){
scanf("%I64d%I64d%I64d",&x,&y,&p);
LL ans=work(x,y,p);
for(LL k=0;k<upp;k++){
if(up[k].pos>=x&&up[k].pos<=y){
bool flag1=coprime(up[k].pos,p);
bool flag2=coprime(up[k].val,p);
if(flag1){
if(flag2){
ans=ans-up[k].pos+up[k].val;
}
else
ans=ans-up[k].pos;
}
else{
if(flag2)
ans=ans+up[k].val;
}
}
}
printf("%I64d
",ans);
}
else{
scanf("%I64d%I64d",&x,&c);
LL i;
for(i=0;i<upp;i++){
if(up[i].pos==x){
up[i].val=c;
}
}
if(i==upp){
up[upp].pos=x;
up[upp].val=c;
upp++;
}
}
}
}
return 0;
}
别人的代码：http://blog.csdn.net/dgq8211/article/details/8031257
#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
",ans);
}
else
{
scanf("%d%d",&a,&b);
M[a] = b;
}
}
}
return 0;
}