首页 > 代码库 > BZOJ 1363 最小公倍数之和

BZOJ 1363 最小公倍数之和

Description

求\(\sum_{i=1}^n[i,n],n\leqslant 10^9,T\leqslant 5\times 10^4\)

Solution

数论+欧拉函数...

破题有毒...

推导和BZOJ 2226: [Spoj 5971] LCMSum一样...

但是需要枚举所有约数,同时统计一下\(\varphi\)...

Code

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int N = 1000050;const ll p = 1e9+7;ll ans,n,x;int b[N],pr[N],cp;ll d[N],c[N],cd;void pre(int n) {	for(int i=2;i<=n;i++) {		if(!b[i]) pr[++cp]=i;		for(int j=1;j<=cp && i*pr[j]<=n;j++) {			b[i*pr[j]]=1;			if(i%pr[j]==0) break;		}	}}void DFS(int x,int s,int ph) {	if(x==cd+1) { if(s!=1) ans=(ans+(ll)s*ph/2)%p;else ans=(ans+1)%p;return; }	DFS(x+1,s,ph);	ph*=(d[x]-1),s*=d[x];	DFS(x+1,s,ph);	for(int i=2;i<=c[x];i++) ph*=d[x],s*=d[x],DFS(x+1,s,ph);}int main() {	int T;	pre(1000000);	for(scanf("%d",&T);T--;) {		scanf("%lld",&n);		cd=0,ans=0,x=n;		for(int i=1;i<=cp && pr[i]*pr[i]<=x;i++) if(x%pr[i]==0) {			d[++cd]=pr[i],c[cd]=0;			for(;x%pr[i]==0;c[cd]++,x/=pr[i]);		}if(x>1) d[++cd]=x,c[cd]=1;		DFS(1,1,1);		printf("%lld\n",ans*n%p);	}	return 0;}

  

BZOJ 1363 最小公倍数之和