1363 最小公倍数之和
题目来源： SPOJ 基准时间限制：1.5 秒 空间限制：131072 KB 分值: 160 给出一个n，求1-n这n个数，同n的最小公倍数的和。 例如：n = 6，1,2,3,4,5,6 同6的最小公倍数分别为6,6,6,12,30,6，加在一起 = 66。 由于结果很大，输出Mod 1000000007的结果。 Input 第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 50000) 第2 - T + 1行：T个数A[i](A[i] <= 10^9) Output 共T行，输出对应的最小公倍数之和 Input示例 3 5 6 9 Output示例 55 66 279思路:这题数据很大，还需要一些剪枝，不然过不去； 首先最小公倍数的和，不考虑时间复杂度， 求法: 首先你需要知道有个这样的定理:如果 gcd(n,i)=1则 gcd(n,n-i)=1 (1<=i<=n) 可得小于n的并与n互质的和为p*phi(p)/2; p=1的时候是特例需要特判+1； 答案显然等于 n * (phi(g) * g / 2 + 1) g | n, g >= 1 显然需要枚举n的因数，最常见sqrt（n）的写法，根据题目T*sqrt（n）显然超时； 优化： 首先你需要知道欧拉函数的两个积性函数的性质：欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
然后将n质因数分解，二进制枚举，这时你会发现万一有多个相同的质数会重复累加，所以将存不同质数，和质数的个数； 在枚举的时候后面的指数跟前面的数不管如何乘必然互质，这就可以用到积性函数的第一个性质； 在处理相同质数，用到第二个质数； 如果p是质数，φ（p）=p-1； #include<bits/stdc++.h> using namespace std; #define ll long long #define mod 1000000007 #define inf 999999999 #define esp 0.00000000001 ll scan() { ll res = 0 , ch ; while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) ) { if( ch == EOF ) return 1 << 30 ; } res = ch - '0' ; while( ( ch = getchar() ) >= '0' && ch <= '9' ) res = res * 10 + ( ch - '0' ) ; return res ; } const int MAXN=32000; int fa[100]; int si[100],p; ll ans; int prime[MAXN],cnt; bool vis[MAXN]; inline int Prime(int n) { cnt=0; memset(vis,0,sizeof(vis)); for(int i=2;i<n;i++) { if(!vis[i]) prime[cnt++]=i; for(int j=0;j<cnt&&i*prime[j]<n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) break; } } return cnt; } inline void dfs(ll fac,ll pos,ll x,ll oula) { if(pos==p) { ans+=oula*fac/2; ans%=mod; return; } ll base=1; ll hh=1; for(int i=0;i<=si[pos];i++) { dfs(fac*base,pos+1,x,oula*hh); base*=fa[pos]; hh*=fa[pos]-(i==0?1:0); } } int main() { ll x,y,z,i,t; Prime(MAXN); int T; scanf("%d",&T); while(T--) { memset(si,0,sizeof(si)); scanf("%lld",&x); ans=0; p=0; z=x; for(i=0;i<cnt&&prime[i]*prime[i]<=z;i++) { if(z%prime[i]==0) { fa[p]=prime[i]; while(z%prime[i]==0) { z/=prime[i]; si[p]++; } p++; } } if(z>1) { fa[p]=z; si[p++]++; } dfs(1,0,x,1); printf("%lld\n",(x*(ans+1))%mod); } return 0; }
转载于:https://www.cnblogs.com/jhz033/p/5776554.html
相关资源：JAVA上百实例源码以及开源项目