SPOJ 5971 lcm sum

题目链接：https://www.spoj.pl/problems/LCMSUM/

SPOJ Problem Set (classical)

5971. LCM Sum

Problem code: LCMSUM

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.

Example

Sample Input :
3
1
2
5

Sample Output :
1
4
55

Constraints

1 <= T <= 300000
1 <= n <= 1000000

这个题目如果用读数优化，可能时间会更快点，不过我没有改了。。

我的代码花了4.27s，可以说是卡过去的。。

这个题，个人感觉非常不错。应该是POJ 2480 gcd sum的升级版。

说一下做法吧。

我最先开始已经推导出：ans=sigma(n/d*eular(n/d)*n/2)

n/2是每一个与n的最大公约数为d的数的平均数。（理论依据是所有小于n的且与n互质的数的和为(1+2+3+..+n)/2,详细内容可以查阅相关资料）

然后说说这个式子怎么转化吧。

其实，n/d*eular(n/d)=d*eular(d)。原因就是d会出现的数字，n/d也一定会出现。

举个例子：n=6,那么d=1,2,3,6 n/d=6,3,2,1

完全一样的说～

然后于是ans=sigma(d*eular(d)*n/2)

这里说说当d=1的时候，这个时候是一个特殊情况。

因为我们这个时候平均数事实上是n，而非n/2

所以式子需要修正：ans=sigma(d*eular(d)*n/2+n/2)

ans=n*sigma(d*eular(d)+1)

注意到上面两个式子在数学上面并不相等，但是由于这里，除号是一个整除法，所以这里，其实两个式子是相等的（至少计算机算出来是一样的）

下面就是我的代码了：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
typedef long long ll;

using namespace std;

bool flag[1000005];
ll prime[1000005];
ll phi[1000005];
ll factor[40];
ll numfac[40];
ll ans;

void init()//得到素数以及欧拉函数值
{
	ll i,j,num=0;
	phi[1]=1;
	for(i=2;i<=1000000;i++)
	{
		if(!flag[i])
		{
			prime[num++]=i;
			phi[i]=i-1;
		}
		for(j=0;j<num&&prime[j]*i<=1000000;j++)
		{
			flag[prime[j]*i]=true;
			if(i%prime[j]==0)
			{
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else
				phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}

ll div(ll n)//分解因数
{
	ll i,num=0;
	for(i=0;prime[i]*prime[i]<=n;i++)
	{
		if(n%prime[i]==0)
		{
			factor[num]=prime[i];
			numfac[num]++;
			n=n/prime[i];
			while(n%prime[i]==0)
			{
				numfac[num]++;
				n=n/prime[i];
			}
			num++;
		}
		if(n==1)
			break;
	}
	if(n>1)
	{
		factor[num]=n;
		numfac[num]++;
		num++;
	}
	return num;
}

void dfs(ll dep,ll k,ll len)//dfs生成因数
{
	if(dep==len)
	{
		ans=ans+k*phi[k]/2;
		return;
	}
	ll tmp=1,i;
	for(i=0;i<=numfac[dep];i++)
	{
		dfs(dep+1,k*tmp,len);
		tmp=tmp*factor[dep];
	}
}

int main()
{
	ll n,t,len;
	init();
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld",&n);
		memset(factor,0,sizeof(factor));
		memset(numfac,0,sizeof(numfac));
		len=div(n);
		ans=0;
		dfs(0,1,len);
		printf("%lld\n",(ans+1)*n);
	}
	return 0;
}