7
18
2016
1

51nod 部分数论题

长期更新

我已经差不多是个打表+优化暴力+卡常选手了

为了方便都用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()]);
}

 

Category: 51nod | Tags: 数论 51nod | Read Count: 996
Avatar_small
Dirak 说:
2016年8月19日 19:11

黄比利真是太强啦


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com