编程 一个数论的题 求解...

Question

已知n(1≤n≤2000000000)，f(n)=lcm(1,n)+ lcm(2,n)+…+ lcm(n,n)，容易证明f(n)能被n整除，输出f(n)/n的值。
lcm(a,b)表示a与b的最小公倍数
例如:
f(1)=1
f(2)=2
f(3)=4
...
这本是个编程题
但数据规模太大了
应该有数学上的一些优化方法
拜托大家了 数学思维...
说下思路就行了

Answer 1

显然，lcm(i,n) (i=1,2,...,n，下面省略)肯定是能被n整除的，所以f(n)能被n整除，因此只要求出lcm(i,n)/n的值就可以了。我是这样分析lcm(i,n)的：它可以由i*n再约去两者的共同因子得到。因此，只要把i中两者的共同因子约去，再把结果相加起来便得到了lcm(i,n)/n。可以首先对n分解质因数，然后用i除以n的各质因数，如果能整除，则在i中约去该因子（因为该因子为两者的共同因子）。对每一个i执行以上步骤后，再把结果加起来就行了。
下面是C语言的完整代码：

#include<stdio.h>

void main()
{
long n, i, j;

printf("请输入数n (1 <= n <= 2000000000) :");
scanf("%ld", &n);

long prmfct[100]; // 存放n的质因数
int index = 0;

// 对n分解质因数
long x = n;
for (i=2; i<=x; i++)
{
while (x != i)
{
if (x%i == 0)
{
prmfct[index] = i;
x = x/i;
index++;
}
else break;
}
}
prmfct[index] = x;

// 求各项的值并相加
long s = 0;
for (i=1; i<=n; i++)
{
x = i;
for (j=0; j<=index; j++)
{
if (x%prmfct[j] == 0)
x /= prmfct[j];
else break;
}
s += x;
}

printf("f(n)/n = %d\n", s);
}