首页 > 代码库 > 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 最小公倍数之和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。