本题关联比赛
20190522数学

关于最小公倍数之和的近10条评论(全部评论)
の神 ┭┮﹏┭┮ 2024-04-06 14:42 11楼
回复 @Mike is Fool : 好尴尬。 kito 2017-01-11 16:20 10楼
回复 @kito : 感谢神犇的悉心指教 FoolMike 2017-01-11 13:54 9楼
AntiLeaf 2017-01-11 09:55 8楼
为什么发了三层......身败名裂...... AntiLeaf 2017-01-11 09:17 7楼
AntiLeaf 2017-01-11 09:16 6楼
回复 @Mike is Fool : 你的式子 $=\sum_{i=1}^{n}\sum_{j=1}^{n}[gcd(i,j)==1]ij$ $=\sum_{i=1}^{n}i\sum_{j=1}^{n}[gcd(i,j)==1]j$ $=2\sum_{i=1}^{n}i\sum_{j=1}^{i}[gcd(i,j)==1]j-\sum_{i=1}^{n}[gcd(i,i)==1]ii$ $=(2\sum_{i=1}^{n}i\sum_{j=1}^{i}[gcd(i,j)==1]j)-1$ 有公式: $\sum_{i=1}^{n}[gcd(i,n)==1]·i=\frac{n\phi(n)+[n==1]}{2}$ 你的式子 $=2\sum_{i=1}^{n}i\frac{i\phi(i)+[i==1]}{2} -1$ $=\sum_{i=1}^{n}ii\phi(i)+1-1$ $=\sum_{i=1}^{n}ii\phi(i)$ kito 2017-01-11 08:27 5楼
谁能证明一下 $\sum_{1<=i,j<=n'and'gcd(i,j)=1}^{} {ij} = \sum_{i=1}^{n} {ii*phi(i)}$ FoolMike 2017-01-04 08:55 4楼
%%%%%%% AntiLeaf 2017-01-03 08:35 3楼
神啊。。。。。。神利·代目 2016-05-26 21:03 2楼

2321. [HZOI 2015]最小公倍数之和

★★★☆ 输入文件：lcm.in 输出文件：lcm.out 简单对比
时间限制：4 s 内存限制：512 MiB

这是一道非常简单的题目

有一天， $QAQ$ 看到了如下程序(貌似是喵星球的语言，不过应该能看懂）：

$ans=0；$

$for(i=1;i<=n;++i)$

$for(j=1;j<=n;++j)$

$ans=ans+lcm(i,j)；$

其中 $lcm(i,j)$ 定义为 $i$ 和 $j$ 的最小公倍数

现在 $QAQ$ 想知道对于给定的 $n，ans$ 的答案是多少

由于 $QAQ$ 非常讨厌写高精度，所以他希望你输出答案对 $1e9+7$ 取模后的结果

输入一个数n

输出相应的答案

对于 $20\%$ 的数据， $n \leq 10000$

对于 $50\%$ 的数据， $n<=10^7$

对于 $80\%$ 的数据， $n<=10^9$

对于 $100\%$ 的数据， $n<=10^{10}$

51Nod