首页 > 代码库 > bzoj 2226: [Spoj 5971] LCMSum 数论
bzoj 2226: [Spoj 5971] LCMSum 数论
2226: [Spoj 5971] LCMSum
Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 578 Solved: 259
[Submit][Status]
Description
Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required sum.
Sample Input
3
1
2
5
1
2
5
Sample Output
1
4
55
4
55
HINT
Constraints
1 <= T <= 300000
1 <= n <= 1000000
这道题将lcm转化为gcd并按照相同gcd分为一组的思路进行，巧妙地将题目转化为求小于等于n且与n互质数的和，而这个值时n*phi(n)/2
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 1000010typedef long long qword;//segma(i*n/gcd(i,n))//=n*segma(h(n/k)/k)//h(a)表示与a互质数的和bool pflag[MAXN];int prime[MAXN],topp=-1;int phi[MAXN];void init(){ int i,j; int x,y; for (i=2;i<MAXN;i++) { if (!pflag[i]) { prime[++topp]=i; phi[i]=i-1; } for (j=0;j<=topp && i*prime[j]<MAXN ;j++) { pflag[i*prime[j]]=true; phi[i*prime[j]]=phi[i]*phi[prime[j]]; if (i%prime[j]==0) { x=i;y=prime[j]; while (x%prime[j]==0) { x/=prime[j]; y*=prime[j]; } if (x==1) { phi[i*prime[j]]=i*(prime[j]-1); }else { phi[i*prime[j]]=phi[x]*phi[y]; } continue; } } }}qword h(int x){ if (x==1)return 1; return (qword)x*phi[x]/2;}int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int nn; int n,i; scanf("%d",&nn); init(); while (nn--) { scanf("%d",&n); qword ans=0; for (i=1;i*i<n;i++) { if (n%i!=0)continue; ans+=(qword)n*h(n/i); ans+=(qword)n*h(i); } if (i*i==n) ans+=(qword)n*h(i); printf("%lld\n",ans); }}
bzoj 2226: [Spoj 5971] LCMSum 数论
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。