长期更新
我已经差不多是个打表+优化暴力+卡常选手了
为了方便都用S(n)表示n*(n+1)/2
1026
为了方便以下用n代指a+n-1,用m代指b+m-1
总的情况减掉重复的数就是所有不同的数。
考虑一个数p满足$a<=p^{sta}<p^{end}<=n$，那么设[sta,end]={a_{1},a_{2},...a_{end-sta+1}
重复的情况就是对于满足一个$\sum_{l=b}^{m}lcm(a_{k1},a_{k2},a_{k3}...a{ks})|l*(-1)^{s+1}$
lcm增长起来非常快所以可以省掉很多冗余的枚举。O(跑得过),V3不会做
#include<cstdio>
using namespace std;
int a,b,n,m,cnt,num,last;
int sta[710],ed[710];
bool vis[1000005];
long long ans;
inline int gcd(int x,int y){return x==0?y:gcd(y%x,x);}
inline int lowbit(int k){return k&-k;}
int main(){
scanf("%d%d%d%d",&m,&n,&a,&b);
ans=1LL*m*n;
m=b+m-1;n=a+n-1;
for(int i=2;i<=n;i++)if(!vis[i]){
long long now=i;
cnt++;
ed[cnt]=1;sta[cnt]=0;
while(now<=n){
if((now>=a)&&(sta[cnt]==0))sta[cnt]=ed[cnt];
ed[cnt]++;
vis[now]=true;
now=now*i;
}
ed[cnt]--;
if((sta[cnt]>=ed[cnt])||(sta[cnt]==0))cnt--;
}
for(int i=1;i<=cnt;i++){
if((sta[i]==sta[i-1])&&(ed[i-1]==ed[i])){ans+=last;continue;}
last=0;
for(int j=3;j<(1<<(ed[i]-sta[i]+1));j++){
if(lowbit(j)==j)continue;
int p=1,Min=0,Max,s=0;
for(int k=sta[i];k<=ed[i];k++)if(j&(1<<(k-sta[i]))){
Max=k;
if(!Min)Min=k;
s++;
p=1LL*p*k/gcd(p,k);
}
Min=p/Min;
Max=p/Max;
if(m/Min-(b-1)/Max<=0)continue;
int tmp;
if(s&1)tmp=m/Min-(b-1)/Max;
else tmp=(b-1)/Max-m/Min;
ans+=tmp;
last+=tmp;
}
}
printf("%lld",ans);
}
1192
原题，但我上次忘记写了_(:зゝ∠)_BZOJ2820gcd=1也就这个套路了
$\sum_{prime(p)}\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}e(gcd(i,j))$
$\sum_{prime(p)}\sum_{d=1}^{n/p}\mu(d)[n/pd]*[m/pd]$
$\sum_{i=1}^{n}[n/i]*[m/i]\sum_{p|i,prime(p)}\mu(i/p)$
$\sum_{p|i,prime(p)}\mu(i/p)$可以线性筛之后线性时间内搞出来，每次询问根号时间枚举n/i和m/i就可以了
#include<cstdio>
using namespace std;
int sum[5000005],f[5000005],last[5000005],prime[670000],s[5000005],mu[5000005],p[5000005];
int n,m,test,cnt;
void pre(int n){
mu[1]=1;
for(int i=2;i<=n;i++){
if(!last[i]){last[i]=1;prime[++cnt]=i;s[i]=1;mu[i]=-1;p[i]=i;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=n);j++){
int k=prime[j]*i;p[k]=prime[j];
if(i%prime[j]==0){last[k]=last[i];s[k]=s[i]+1;mu[k]=0;break;}
else{last[k]=i;s[k]=1;mu[k]=-mu[i];}
}
}
}
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
int main(){
pre(5000000);
for(int i=2;i<=5000000;i++){
if(s[i]==1)f[i]=-f[last[i]]+mu[last[i]];
else if(s[i]==2)f[i]=mu[i/p[i]];
else f[i]=0;
sum[i]=sum[i-1]+f[i];
}
test=read();
while(test--){
n=read();m=read();
if(n>m){int t=n;n=m;m=t;}
int kn=1,km=m/n,last=n;
long long ans=0;
while(true){
int x=min(last-1,max(n/(kn+1),m/(km+1)));
ans+=1LL*(sum[last]-sum[x])*kn*km;
if(x==0)break;
last=x;kn=n/x;km=m/x;
}
printf("%lld\n",ans);
}
}
1237
先套路
$\sum_{d=1}^{n}d\sum_{k=1}^{n/d}\mu(k)([n/dk])^{2}$
$\sum_{i=1}^{n}([n/i])^{2}\sum_{d|i}\mu(d)*i/d$
考虑$\sum_{d|i}\mu(d)*i/d$的前缀和之后就可以枚举n/i做
$\sum_{i=1}^{n}\sum_{d|i}\mu(d)*i/d=\sum_{i=1}^{n}\mu(i)*S(n/i)$
非常显然这个东西我们可以结合杜教筛做到每次$O(\sqrt{n})$时间算
总复杂度$O(n^{0.75})$需要卡常_(:зゝ∠)_
#include<cstdio>
#include<cmath>
#define size 4641588
#define mo 1000000007
using namespace std;
int A[2200],mu[size+5],prime[500005];
int v[100005],V[100005],s[100005],S[100005];
//wo you te shu de ka chang ji qiao
bool vis[size+5];
long long n;
int ans,cnt,ny,si;
void pre(){
mu[1]=1;
for(int i=2;i<=size;i++){
if(!vis[i]){vis[i]=true;prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
}
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline int workmu(long long k){
if(k<=size)return mu[k];
if(A[n/k])return A[n/k];
int ans=1;
long long last=k,p=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-(last-x)%mo*workmu(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;return ans;
}
inline int work(long long k){
if(k<=si)return s[k];
else return S[n/k];
}
inline int workv(long long k){
if(k<=si)return v[k];
else return V[n/k];
}
inline int f(long long k){
int ans=0;
for(int i=1;1LL*i*i<=k;i++){
ans=(ans+1LL*workv(i)*(work(k/i)-work(k/(i+1))))%mo;
if(k/i!=i)ans=(ans+1LL*workv(k/i)*i)%mo;
}
if(ans<0)ans+=mo;
return ans;
}
int main(){
scanf("%lld",&n);si=int(sqrt(n));
pre();
for(int i=2;i<=size;i++)mu[i]+=mu[i-1];ny=pow(2,mo-2);
for(int i=1;i<=si;i++)v[i]=1LL*i*i%mo,V[i]=((n/i)%mo)*((n/i)%mo)%mo,s[i]=1LL*i*(i+1)/2%mo,S[i]=(n/i%mo)*((n/i+1)%mo)%mo*ny%mo;
long long last=n,p=1;
while(true){
long long x=min(last-1,n/(p+1));
if(workmu(last)-workmu(x)!=0)ans=(1LL*(workmu(last)-workmu(x))*f(p)+ans)%mo;
if(x==0)break;
last=x;p=n/last;
}
if(ans<0)ans+=mo;
printf("%d",ans);
}
1238
这个世界充满了套路
$\sum_{d=1}^{n}d\sum_{k=1}^{n/d}\mu(k)k^{2}(S[n/dk])^{2}$
$\sum_{i=1}^{n}(S[n/i])^{2}i\sum_{d|i}\mu(d)*d$
其他一样
也需要卡常_(:зゝ∠)_
#include<cstdio>
#define size 4641588
#define mo 1000000007
using namespace std;
long long n;
int ny,cnt,ans,ny3;
int mu[size+5],prime[400000],A[3000],trick[100005],Trick[100005];
bool vis[size+5];
inline long long min(long long x,long long y){return x<y?x:y;}
inline int sqr(int k){return 1LL*k*k%mo;}
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
void pre(){
mu[1]=1;
for(int i=2;i<=size;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
for(int i=2;i<=size;i++)mu[i]=((1LL*mu[i]*i*i+mu[i-1])%mo+mo)%mo;
}
inline int F(long long k){
int t=k%mo;
return 1LL*t*(t+1)%mo*(2*t+1)%mo*ny%mo*ny3%mo;
}
inline int workmu(long long k){
if(k<=size)return mu[k];
if(A[n/k])return A[n/k];
long long last=k,p=1;int ans=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-1LL*(F(last)-F(x))*workmu(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
inline int W(long long k){
if(k==0)return 0;
if(n/k>k)return trick[k];
else return Trick[n/k];
}
inline int f(long long k){
if(k==0)return 0;
int ans=0;
for(int i=1;1LL*i*i<=k;i++){
ans=(ans+1LL*i*workmu(k/i))%mo;
if(k/i!=i)ans=(ans+1LL*(W(k/i)-W(k/(i+1)))*mu[i])%mo;
}
if(ans<0)ans+=mo;
return ans;
}
int main(){
scanf("%lld",&n);
pre();ny=pow(2,mo-2);ny3=pow(3,mo-2);
for(int i=1;1LL*i*i<=n;i++){
trick[i]=1LL*i*(i+1)/2%mo;
int t=(n/i)%mo;
Trick[i]=1LL*t*(t+1)%mo*ny%mo;
}
long long last=n,p=1;int flast=f(last);
while(true){
long long x=min(last-1,n/(p+1));int t=p%mo,fx=f(x);
ans=(ans+1LL*sqr(1LL*(t+1)*t%mo*ny%mo)*(flast-fx))%mo;
if(x==0)break;
flast=fx;last=x;p=n/x;
}
if(ans<0)ans+=mo;
printf("%d\n",ans);
}
1239
模板，为了整齐还是放一下吧
#include<cstdio>
#define mo 1000000007
#define size 4641588
using namespace std;
int cnt,ny;
long long n;
long long A[3000],phi[size+5];
int prime[500005];
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
void pre(){
phi[1]=1;
for(int i=2;i<=size;i++){
if(!phi[i]){prime[++cnt]=i;phi[i]=i-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
if(i%prime[j]==0){phi[k]=phi[i]*prime[j];break;}
else phi[k]=phi[i]*(prime[j]-1);
}
}
for(int i=2;i<=size;i++)phi[i]=(phi[i]+phi[i-1])%mo;ny=pow(2,mo-2);
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline int work(long long k){
if(k<=size)return phi[k];
if(A[n/k])return A[n/k];
int t=k%mo;
int ans=1LL*t*(t+1)%mo*ny%mo;
long long last=k,p=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-(last-x)%mo*work(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
int main(){
scanf("%lld",&n);
pre();
printf("%d",work(n));
}
1244
同模板
#include<cstdio>
#define mo 1000000007
#define size 4641588
using namespace std;
int cnt,ny;
long long n;
long long A[3000],phi[size+5];
int prime[500005];
inline int pow(int x,int k){
int ans=1;
for(;k;k>>=1,x=1LL*x*x%mo)if(k&1)ans=1LL*x*ans%mo;
return ans;
}
void pre(){
phi[1]=1;
for(int i=2;i<=size;i++){
if(!phi[i]){prime[++cnt]=i;phi[i]=i-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
if(i%prime[j]==0){phi[k]=phi[i]*prime[j];break;}
else phi[k]=phi[i]*(prime[j]-1);
}
}
for(int i=2;i<=size;i++)phi[i]=(phi[i]+phi[i-1])%mo;ny=pow(2,mo-2);
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline int work(long long k){
if(k<=size)return phi[k];
if(A[n/k])return A[n/k];
int t=k%mo;
int ans=1LL*t*(t+1)%mo*ny%mo;
long long last=k,p=1;
while(true){
long long x=min(last-1,k/(p+1));
ans=(ans-(last-x)%mo*work(p))%mo;
if(x==1)break;
last=x;p=k/x;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
int main(){
scanf("%lld",&n);
pre();
printf("%d",work(n));
}
1220
终于不是套路了
我们先证一个结论
$d(n*m)=\sum_{i|n}\sum_{j|m}n/i*j*e(gcd(i,j))$
考虑单个素数对答案的贡献，设$n=N*p^{a}$,$m=M*p^{b}$
$d(n*m)=d(N*M)*d(p^{a+b})=d(N*M)*(1+p+...+p^{a+b-1}+p^{a+b})$
$\sum_{i|p^{a}}\sum_{j|p^{b}}n/i*j*e(gcd(i,j))=1+p+...+p^{a+b-1}+p^{a+b}$
简单归纳一下就可以得到那个结论
其实我是从BZOJ3994想到的
$\sum_{i=1}^{n}\sum_{j=1}^{n}d(i*j)=\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{a|i}\sum_{b|j}i/a*b*e(gcd(a,b))$
$\sum_{i=1}^{n}\sum_{j=1}^{n}S(n/i)*j*[n/j]*e(gcd(i,j))$
$\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{n/d}S(n/i/d)\sum_{j=1}^{n/d}j*d*[n/j/d]$
$\sum_{d=1}^{n}\mu(d)d(\sum_{i=1}^{n/d}[n/d/i])^{2}$
因为套路题磨练出的卡常技巧好像跑得很快_(:зゝ∠)_
#include<cstdio>
#define mo 1000000007
#define m 1000000
using namespace std;
int mu[m+5],prime[100005];
int n,ans,cnt;
int A[1005];
bool vis[m+5];
void pre(){
mu[1]=1;
for(int i=2;i<=m;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=m);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
for(int i=2;i<=m;i++){
mu[i]=mu[i]*i+mu[i-1];
if(mu[i]<0)mu[i]+=mo;
if(mu[i]>=mo)mu[i]-=mo;
}
}
inline int min(int x,int y){return x<y?x:y;}
inline int f(int k){
int last=k,p=1,ans=0;
for(int i=1;i*i<=k;i++){
ans=(ans+1LL*i*(i+1)/2*(k/i-k/(i+1)))%mo;
if(k/i!=i)ans=(ans+1LL*(k/i)*(k/i+1)/2)%mo;
}
return 1LL*ans*ans%mo;
}
inline int workmu(int k){
if(k<=m)return mu[k];
if(A[n/k])return A[n/k];
int ans=1;
for(int i=1;i*i<=k;i++){
if((i>1)&&(k/i!=i))ans=(ans-1LL*workmu(k/i)*i)%mo;
ans=(ans-1LL*(k/i+k/(i+1)+1)*(k/i-k/(i+1))/2%mo*mu[i])%mo;
}
if(ans<0)ans+=mo;A[n/k]=ans;
return ans;
}
int main(){
scanf("%d",&n);
pre();
int last=n,p=1;
while(true){
int x=min(last-1,n/(p+1));
ans=(ans+1LL*(workmu(last)-workmu(x))*f(p))%mo;
if(x==0)break;
last=x;p=n/x;
}
if(ans<0)ans+=mo;
printf("%d",ans);
}
1223
假设$gcd(x,y)=d,x=ad,y=bd,x<y$
$\frac{1}{ad}+\frac{1}{bd}=\frac{a+b}{abd}$
因为a,b互质所以非常显然a+b和a互质,a+b和b互质，所以a+b和ab互质
所以d能被a+b整除，同时要满足$bd<=n$
$\sum_{a=1}^{n}\sum_{b=a+1}^{n}e(gcd(a,b))*n/(a+b)/b$
$\sum_{d=1}^{n}\mu(d)\sum_{b=2}^{n/d}\sum_{a=1}^{b-1}[n/(a+b)/b]$
显然实际枚举的时候b大于$\sqrt{n}$对答案没有贡献，对a的枚举也一样，然后就可以显著地减少枚举，O(跑得过)
#include<cstdio>
#include<cmath>
using namespace std;
long long n,ans;
int cnt,size,last,s;
int mu[400005],prime[30005];
bool vis[400005];
inline long long min(long long x,long long y){return x<y?x:y;}
void pre(){
mu[1]=1;
for(int i=2;i<=size;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=size);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
}
inline long long f(long long s,int l,int r){
long long ans=0;
if(r>s)r=s;
int last=r;
long long p=s/r;
while(true){
int x=min(last-1,s/(p+1));
if(x<l){ans+=p*(last-l+1);break;}
ans+=p*(last-x);
last=x;p=s/x;
}
return ans;
}
inline int long long work(long long p){
long long ans=0;
for(int i=2;1LL*i*(i+1)<=p;i++)ans+=f(p/i,i+1,2*i-1);
return ans;
}
int main(){
scanf("%lld",&n);
size=int(sqrt(n));
pre();last=-1;
for(int i=1;i<=size;i++)if(mu[i])ans+=mu[i]*work(n/i/i);
printf("%lld",ans);
}
1602
非常显然x就是$\mu(i)$因为$\sum_{d|i}\mu(d)=e(i)$
问题变成了求$\mu(i)=x$的第k小解
考虑二分答案，$\sum_{i=1}^{n}\mu(i)$可以杜教筛，我们考虑$\sum_{i=1}^{n}|\mu(i)|$
$\sum_{i=1}^{n}\left | \mu(i)\right |$可以洲爷筛，但是太慢了我们不能接受。
简单地容斥一下可以发现$\sum_{i=1}^{n}|\mu(i)|=\sum_{i=1}^{\sqrt{n}}[n/i^{2}]*\mu(i)$
$\sum_{i=1}^{n}|\mu(i)|=\sum_{i=1}^{\sqrt{n}}[n/i^{2}]*\mu(i)$我们就可以直接暴力在$O(\sqrt{n})$的时间内算出
设$ans1=\sum_{i=1}^{n}\mu(i)$,$ans2=\sum_{i=1}^{n}\left | \mu(i)\right |$
那么$\sum_{i=1}^{n}|\mu(i)=0|=n-ans2$
$\sum_{i=1}^{n}|\mu(i) =1|=\frac{ans1+ans2}{2}$
$\sum_{i=1}^{n}|\mu(i) =-1|=\frac{ans2-ans1}{2}$
注意因为要多次杜教筛所以杜教筛的m适当开大会比较好面向数据调参大约5000W-7000W会比较好。
调参之后还是过不了就要像我一样分段打表减少二分上下界_(:зゝ∠)_
#include<cstdio>
#include<algorithm>
#define m 70000000
using namespace std;
int mu[m+5],p,cnt;
long long o,n;
int a[2005];
long long t[2005];
long long table0[]={0,98696539ll,197390590ll,296090773ll,394785811ll,493478717ll,592174619ll,690865539ll,789573419ll,888269506ll,986963617ll,1085638187ll,1184353249ll,1283058453ll,1381753534ll,1480438790ll,1579123499ll,1677833470ll,1776525191ll,1875223162ll,1973931083ll,2072625209ll,2171327727ll,2270010614ll,2368701689ll,2467400871ll,2566083487ll,2664774382ll,2763486298ll,2862171758ll,2960878366ll,3059601391ll,3158288941ll,3256989389ll,3355689863ll,3454377809ll,3553053738ll,3651737802ll,3750418478ll,3849108369ll,3947816126ll,4046541778ll,4145229385ll,4243939458ll,4342618289ll,4441315945ll,4540020235ll,4638728678ll,4737406890ll,4836101882ll,4934800549ll,5033493691ll,5132213873ll,5230910298ll,5329603785ll,5428313846ll,5527000218ll,5625677806ll,5724366653ll,5823061145ll,5921763357ll,6020450645ll,6119140105ll,6217818269ll,6316515511ll,6415221166ll,6513923318ll,6612592645ll,6711292427ll,6809993799ll,6908712746ll,7007411354ll,7106109843ll,7204816138ll,7303529521ll,7402221537ll,7500928390ll,7599639885ll,7698355851ll,7797058563ll,7895737187ll,7994415551ll,8093084541ll,8191784013ll,8290456598ll,8389140990ll,8487847905ll,8586540758ll,8685256349ll,8783960642ll,8882642026ll,8981338753ll,9080028929ll,9178727618ll,9277421983ll,9376117705ll,9474818718ll,9573507146ll,9672186455ll,9770872962ll,9869555098ll,9968249813ll,10000000001ll};
long long table1[]={0,76516436ll,153032768ll,229549144ll,306065450ll,382581992ll,459098343ll,535614471ll,612131050ll,688647396ll,765163884ll,841680268ll,918196704ll,994713003ll,1071229320ll,1147745600ll,1224262084ll,1300778556ll,1377294908ll,1453811249ll,1530327700ll,1606844004ll,1683360388ll,1759876625ll,1836393076ll,1912909668ll,1989426024ll,2065942540ll,2142458912ll,2218975339ll,2295491616ll,2372007816ll,2448524196ll,2525040650ll,2601557060ll,2678073327ll,2754589864ll,2831106220ll,2907622467ll,2984138991ll,3060655493ll,3137171884ll,3213688131ll,3290204276ll,3366720488ll,3443236892ll,3519753282ll,3596269536ll,3672785943ll,3749302512ll,3825819100ll,3902335533ll,3978851916ll,4055368248ll,4131884655ll,4208400882ll,4284917544ll,4361433950ll,4437950319ll,4514466904ll,4590983132ll,4667499567ll,4744016032ll,4820532561ll,4897048888ll,4973565245ll,5050081532ll,5126597800ll,5203114182ll,5279630542ll,5356146906ll,5432663284ll,5509179460ll,5585695920ll,5662212272ll,5738728698ll,5815244964ll,5891761360ll,5968277916ll,6044794209ll,6121310832ll,6197827338ll,6274343648ll,6350859850ll,6427376220ll,6503892598ll,6580408772ll,6656925240ll,6733441548ll,6809957936ll,6886474320ll,6962990778ll,7039507145ll,7116023466ll,7192539908ll,7269056127ll,7345572664ll,7422089041ll,7498605338ll,7575121755ll,7651638261ll,7728154632ll,7804671039ll,7881187707ll,7957703888ll,8034220149ll,8110736448ll,8187252916ll,8263769248ll,8340285728ll,8416802132ll,8493318525ll,8569835043ll,8646351180ll,8722867615ll,8799383988ll,8875900375ll,8952416780ll,9028933112ll,9105449301ll,9181965652ll,9258482256ll,9334998621ll,9411515184ll,9488031604ll,9564547850ll,9641064416ll,9717580728ll,9794097112ll,9870613308ll,9947129778ll,10000000001ll};
long long table2[]={0,98695734ll,197393759ll,296085470ll,394782419ll,493481806ll,592178047ll,690879445ll,789563222ll,888259434ll,986957195ll,1085675215ll,1184352063ll,1283038665ll,1381735834ll,1480442462ll,1579149706ll,1677832129ll,1776532638ll,1875226555ll,1973910394ll,2072608571ll,2171298219ll,2270007230ll,2368708266ll,2467401414ll,2566110963ll,2664812038ll,2763492203ll,2862198649ll,2960884319ll,3059552974ll,3158257565ll,3256949471ll,3355641371ll,3454345331ll,3553061986ll,3651769934ll,3750480703ll,3849182731ll,3947866995ll,4046533977ll,4145238465ll,4243920370ll,4342633341ll,4441327994ll,4540015657ll,4638698898ll,4737412873ll,4836109691ll,4934803611ll,5033502835ll,5132174195ll,5230870181ll,5329569021ll,5428251282ll,5526957066ll,5625671179ll,5724374574ll,5823072237ll,5921761942ll,6020466854ll,6119169254ll,6217883243ll,6316577914ll,6415264831ll,6513954815ll,6612677638ll,6711369549ll,6810060517ll,6908733565ll,7007427273ll,7106120474ll,7204806518ll,7303485191ll,7402185281ll,7500869947ll,7599550649ll,7698226571ll,7796916119ll,7895629382ll,7994343758ll,8093066557ll,8191759205ll,8290478699ll,8389186818ll,8487871827ll,8586570670ll,8685247539ll,8783935197ll,8882645819ll,8981341241ll,9080043461ll,9178737087ll,9277434545ll,9376130469ll,9474821742ll,9573525386ll,9672238317ll,9770943295ll,9869652770ll,9968351223ll,10000000001ll};
int prime[5000000];
bool vis[m+5];
inline int workmu(long long k){
if(k<=m)return mu[k];
if(t[o/k]==o)return a[o/k];
int ans=1;
for(int i=1;k/i>=i;i++){
if(i>1)ans-=workmu(k/i);
if(k/i!=i)ans-=mu[i]*(k/i-k/(i+1));
}
t[o/k]=o;a[o/k]=ans;
return ans;
}
inline long long workMu(long long k){
long long ans=0;
for(int i=1;1LL*i*i<=k;i++)ans+=(k/i/i)*(mu[i]-mu[i-1]);
return ans;
}
void pre(){
mu[1]=1;
for(int i=2;i<=m;i++){
if(!vis[i]){prime[++cnt]=i;mu[i]=-1;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=m);j++){
int k=prime[j]*i;
vis[k]=true;
if(i%prime[j]==0){mu[k]=0;break;}
else mu[k]=-mu[i];
}
}
for(int i=1;i<=m;i++)mu[i]+=mu[i-1];
}
inline long long check(long long mid,int p){
o=mid;
long long ans1=workMu(o),ans2=workmu(o);
if(p==0)return o-ans1;
else if(p==1)return (ans1+ans2)/2;
else return (ans1-ans2)/2;
}
int main(){
scanf("%d%I64d",&p,&n);
pre();
long long l,r;
if(p==-1)l=table0[(n-1)/30000000],r=table0[(n-1)/30000000+1];
if(p==0)l=table1[(n-1)/30000000],r=table1[(n-1)/30000000+1];
if(p==1)l=table2[(n-1)/30000000],r=table2[(n-1)/30000000+1];
while(r-l>1){
long long mid=(l+r)>>1;
if(check(mid,p)>=n)r=mid;
else l=mid;
}
printf("%I64d\n",r);
}
1584
因为自己太傻了看不懂题解只好自己YY...
1220的思路,$\sigma (i*j)=\sum_{a|i}\sum_{b|j}i/a*b*e(gcd(a,b))$
$\sum_{i=1}^{n}\sum_{j=1}^{n}max(i,j)\sum_{a|i}\sum_{b|j}i/a*b\sum_{d|(a,b)}\mu(d)$
$\sum_{i=1}^{n}\sum_{j=1}^{n}max(i,j)\sum_{d|(i,j)}\mu(d)\sum_{a|\frac{i}{d}}\sum_{b|\frac{j}{d}}i/a*b$
$\sum_{i=1}^{n}\sum_{j=1}^{n}max(i,j)\sum_{d|(i,j)}\mu(d)d\sum_{a|\frac{i}{d}}\sum_{b|\frac{j}{d}}a*b$
$\sum_{d=1}^{n}\mu(d)d^{2}\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}max(i,j)\sigma(i)\sigma(j)$
$\mu(d)d^{2}$的前缀和我们可以线性筛，后面那个东西线性筛处理出约数和之后瞎搞一下也很好搞出来。
现在我们的问题变成了求$\sum_{i=1}^{n}\sum_{d|i}g(d)*f(i/d)$的形式，假如f和g函数都是积性函数的话这个函数也是积性函数。
但是很遗憾后面那坨东西并不是积性函数_(:зゝ∠)_
然后我在那边写$O(T\sqrt{n})$写了半天，我卡到1.2s还以为是自己被卡常了_(:зゝ∠)_
然而这个东西是可以$O(nlog)$预处理的，只要对于每一个i，枚举一个j,i*j<=n,ans[i*j]+=g(i)*f(j)就可以了_(:зゝ∠)_
每次询问O(1)
#include<cstdio>
#include<ctime>
#define mo 1000000007
using namespace std;
int f[1000005],prime[100005],mu[1000005],last[1000005],s[1000005],ans[1000005];
int cnt,n,test;
inline int read(){
int ret=0;
char c=getchar();
while((c>'9')||(c<'0'))c=getchar();
while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
return ret;
}
void pre(){
mu[1]=1;f[1]=1;
for(int i=2;i<=1000000;i++){
if(!last[i]){last[i]=1;s[i]=i+1;mu[i]=-1;prime[++cnt]=i;}
for(int j=1;(j<=cnt)&&(prime[j]*i<=1000000);j++){
int k=prime[j]*i;
if(i%prime[j]==0){s[k]=s[i]*prime[j]+1,last[k]=last[i],mu[k]=0;break;}
else s[k]=prime[j]+1,last[k]=i,mu[k]=-mu[i];
}
}
for(int i=2;i<=1000000;i++)f[i]=f[last[i]]*s[i],mu[i]=1LL*mu[i]*i*i%mo;
int s=1;
for(int i=2;i<=1000000;i++){
s=(s+f[i])%mo;
f[i]=1LL*((s<<1)-f[i])*f[i]%mo*i%mo;
}
for(int i=1;i<=1000000;i++)
for(int j=1;j*i<=1000000;j++)ans[i*j]=(ans[i*j]+1LL*f[i]*mu[j])%mo;
for(int i=2;i<=1000000;i++)ans[i]=(ans[i]+1LL*ans[i-1]+mo)%mo;
}
int main(){
pre();
test=read();
for(int I=1;I<=test;I++)printf("Case #%d: %d\n",I,ans[read()]);
}
2016年8月19日 19:11
黄比利真是太强啦