作业帮 > 综合 > 作业

一个数论的题 ..已知n(1≤n≤2000000000),f(n)=lcm(1,n)+ lcm(2,n)+…+ lcm(

来源:学生作业帮 编辑:百度作业网作业帮 分类:综合作业 时间:2024/05/14 02:26: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的值太大了,不过既然是编程题,可以优化一下最小公倍数函数