hdu 4407 Sum 容斥+離線
求X-Y之間和p互質的數的和，典型的容斥問題，求和用等差數列求和，注意首項末項是多少。
首先記錄下不修改的答案，離線處理，存下詢問，輸出的時候，遇到一個操作1，就遍歷前面的操作，把修改加上去，注意要判重，只保留最後一次修改。
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll ans;
int pri[1234];
int top;
int n,m,a,b,c;
ll gcd(ll a,ll b)
{
return a%b==0?b:gcd(b,a%b);
}
ll cal(ll num)
{
int x=a;
int y=b;
int fir;
int tmp=y/num-x/num;
if(x%num==0) fir=x,tmp++;
else fir=num*(x/num+1);
if(fir>y) return 0;
int en=fir+(tmp-1)*num;
return (fir+en)*1ll*tmp/2;
}
void dfs(int p,ll num,int flag)
{
if(num>b) return;
if(p) {ans+=flag*cal(num);}
for(int i=p+1;i1) pri[top++]=c;
dfs(0,1,-1);
out[i]=(a+b)*1ll*(b-a+1)/2-ans;
}
else
{
scanf("%d%d",&b,&c);
d[i][1]=b;
d[i][2]=c;
}
}
for(int i=1;i<=m;i++)
{
if(d[i][0]==1)
{
ll ans=out[i];
int cnt=0;
for(int j=i-1;j>=1;j--)
{
if(d[j][0]==2&&!vis[d[j][1]])
{
vis[d[j][1]]=true;
rec[cnt][0]=d[j][1];
rec[cnt][1]=d[j][2];
cnt++;
}
}
for(int j=0;j=d[i][1]&&rec[j][0]<=d[i][2])
{
ans-=( gcd(rec[j][0],d[i][3])==1?rec[j][0]:0 );
ans+=( gcd(rec[j][1],d[i][3])==1?rec[j][1]:0 );
}
}
printf("%I64d\n",ans);
}
}
}
return 0;
}
/*
123
100 1
1 1 10 11
2 2 3
2 2 5
1 1 10 2
*/
