编程一个数论的题..已知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)=1f(2)=2f(3)=4...这本是个编程题但数据规模太

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
void main()
{
long n, i, j;
printf("请输入数n (1