大师作文网编程 一个数论的题 ..
来源：学生作业帮 编辑：大师作文网作业帮 分类：综合作业 时间：2024/11/11 14:24:33
编程 一个数论的题 ..
已知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
...
这本是个编程题
但数据规模太大了
应该有数学上的一些优化方法
说下思路就行了
已知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
...
这本是个编程题
但数据规模太大了
应该有数学上的一些优化方法
说下思路就行了
显然,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
下面是C语言的完整代码：
#include
void main()
{
long n, i, j;
printf("请输入数n (1