乞讨X-Y之间p素数，，典型的纳入和排除问题，列的求和运算总和的数，注意，第一项是最后一个项目数。
如果不改变到第一记录的答案，脱机处理，能保存查询，候，遇到一个操作1，就遍历前面的操作。把改动加上去，注意要判重。仅仅保留最后一次改动。
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
#include<cstring>
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;i<top;i++)
{
dfs(i,pri[i]*num,-flag);
}
}
ll out[1234];
int d[1234][4];
int rec[1234][2];
bool vis[400005];
bool V[400005];
int prime[400005];
int topp=0;
void sieve(int n)
{
int m= (int)sqrt(n+0.5);
for(int i=2;i<=m;i++)
{
if(!V[i])
{
for(int j=i*i;j<=n;j+=i)
V[j]=1;
}
}
V[1]=1;
for(int i=2;i<=400000;i++)
{
if(V[i]==0) prime[topp++]=i;
}
}
int main()
{
sieve(400005);
int cas;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&m);
int op;
for(int i=1;i<=m;i++)
{
scanf("%d",&op);
d[i][0]=op;
if(op==1)
{
ans=0;
top=1;
scanf("%d%d%d",&a,&b,&c);
d[i][1]=a;
d[i][2]=b;
d[i][3]=c;
if(c==1)
{
out[i]=(a+b)*1ll*(b-a+1)/2;
continue;
}
for(int j=0;prime[j]*prime[j]<=c;j++)
{
if(V[c]==0) break;
if(c%prime[j]==0)
{
pri[top++]=prime[j];
while(c%prime[j]==0) c/=prime[j];
}
}
if(c>1) 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<cnt;j++)
{
vis[rec[j][0]]=false;
if(rec[j][0]>=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
*/
版权声明：本文博主原创文章，博客，未经同意不得转载。