数论 CQOI2017:输出文件 table.out。输出共m行,每次操作之后输出1行,表示答案mod 1,000,000,007之后的结果。
这样一个傻逼题为什么当时不A
观察式子
对于每一组,比如第
然后考场上我就在第二个等式之后卡住咯。。。
求出
#include#include #include template void Read(T &x){ char c; bool f(0); while(c=getchar(),c!=EOF) if(c=='-') f=1; else if(c>='0'&&c<='9'){ x=c-'0'; while(c=getchar(),c>='0'&&c<='9') x=x*10+c-'0'; ungetc(c,stdin); if(f) x=-x; return; } } #define MOD 1000000007 #define MAXN 4000000 int p[MAXN+10],pcnt,sk[MAXN+10],phi[MAXN+10],bl[MAXN+10]; int n,m; bool f[MAXN+10]; void prepare(){ int i,j; phi[1]=1; sk[1]=1; for(i=2;i<=n;i++){ if(!f[i]){ phi[i]=i-1; p[++pcnt]=i; } for(j=1;i*p[j]<=n;j++){ f[i*p[j]]=1; if(i%p[j]==0){ phi[i*p[j]]=phi[i]*p[j]; break; } phi[i*p[j]]=phi[i]*phi[p[j]]; } sk[i]=(sk[i-1]+1ll*phi[i]*i%MOD*i)%MOD; } } long long tms[MAXN+10],in[MAXN+10],out[MAXN+10]; int gcd(int a,int b){ int t; while(b){ t=a%b; a=b; b=t; } return a; } int lowbit(int x){ return x&-x; } void update(int x,int d){ for(int i=x;bl[x]==bl[i];i++) in[i]+=d; for(int i=bl[x]+1;i<=bl[n];i++) out[i]+=d; } long long get_sum(int x){ return out[bl[x]]+in[x]; } void read(){ Read(m),Read(n); int t=sqrt(n); for(int i=1;i<=n;i++) bl[i]=(i+t-1)/t; for(int i=1;i<=n;i++) in[i]=in[i-1]+(tms[i]=(1ll*i*i)%MOD); } int Sum(int n){ return 1ll*n*(n+1)/2%MOD; } void solve(){ long long i,a,b,k,d; long long x; while(m--){ Read(a),Read(b),Read(x),Read(k); d=gcd(a,b); update(d,-tms[d]); tms[d]=x/(1ll*a*b/d/d)%MOD; update(d,tms[d]); long long tt; long long ans=0; for(i=1;i<=k;i=tt+1){ tt=k/(k/i); long long ttt=(get_sum(tt)-get_sum(i-1))%MOD,ret(0); ret=sk[k/i]; ans=((ans+ttt*ret)%MOD+MOD)%MOD; } printf("%lld\n",ans); } } int main() { read(); prepare(); solve(); }
我辜负了出题人的良苦用心。