2226: [Spoj 5971] LCMSum
Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 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 1000010
typedef 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=-;
int phi[MAXN];
void init()
{
int i,j;
int x,y;
for (i=;i<MAXN;i++)
{
if (!pflag[i])
{
prime[++topp]=i;
phi[i]=i-;
}
for (j=;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]==)
{
x=i;y=prime[j];
while (x%prime[j]==)
{
x/=prime[j];
y*=prime[j];
}
if (x==)
{
phi[i*prime[j]]=i*(prime[j]-);
}else
{
phi[i*prime[j]]=phi[x]*phi[y];
}
continue;
}
}
}
}
qword h(int x)
{
if (x==)return ;
return (qword)x*phi[x]/;
}
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=;
for (i=;i*i<n;i++)
{
if (n%i!=)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);
}
}