Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
34621 | baka24 | 【S】T1 | C++ | 通过 | 100 | 4 MS | 8076 KB | 1263 | 2024-11-12 13:38:00 |
//100 #include<bits/stdc++.h> using namespace std; #define int long long int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=1000010,Mod=1000000007; int l,r,inv,a[MAXN],ans; int Pow(int x,int y){int rt=1;while(y){if(y&1)rt=rt*x%Mod;x=x*x%Mod;y>>=1;}return rt;} int f(int x){ return (x+x*(x-1)%Mod*inv%Mod+(x-1)*x%Mod*inv%Mod*(x+1)%Mod*(x+2)%Mod*inv%Mod)%Mod; } int g(int x){ return (f(x)-8*f(x/2)%Mod*2%Mod)%Mod; } int h(int x){ return (g(x)*2%Mod+(x&1?x/2+1:-x/2)%Mod)%Mod; } int t(int l,int r){ return (l+r)%Mod*(r-l+1)%Mod*inv%Mod; } int sol(int x){ int p=sqrt(x); int res=h(p); if(x>p+p*p)res+=t(p*p+p+1,x)*(p&1?-1:1); else res-=t(x+1,p+p*p)*(p&1?1:-1); res%=Mod; return res; } void slv(){ inv=Pow(2,Mod-2); l=read(),r=read(); if(r<=1000000){ for(int i=1,f=1,r=2,j=4;i<=1000000;i++){ a[i]=i*f; if(i==r)f=-f,r+=j,j+=2; } for(int i=l;i<=r;i++)ans+=a[i],ans%=Mod; printf("%lld",(ans+Mod)%Mod); } else printf("%lld",((sol(r)-sol(l-1))%Mod+Mod)%Mod); } signed main(){ slv(); return 0; }