Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
BZOJ2226: [Spoj 5971] LCMSum
? 解题记录 ?
? BZOJ ?
? 欧拉函数 ?
2018-01-30 22:12:04
300
0
0
rockdu
? 解题记录 ?
? BZOJ ?
? 欧拉函数 ?
<font color = blue>Description</font> Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n. <font color = blue>Input</font> The first line contains T the number of test cases. Each of the next T lines contain an integer n. <font color = blue>Output</font> Output T lines, one for each test case, containing the required sum. <font color = blue>Sample Input</font> 3 1 2 5 <font color = blue>Sample Output</font> 1 4 55 HINT 1 <= T <= 300000 1 <= n <= 1000000 Source 大意：$$\sum^n_{i=1}lcm(i, n)$$ 经历过升级版的人当然无所畏惧。化简原式 $$\sum^n_{i=1}\frac{i\cdot n}{gcd(i,n)}=\sum_{d|n}\sum^n_{i=1}[gcd(i, n)=d]\frac{i\cdot n}{d}\\ =n\cdot \sum_{d|n}\sum^{\frac{n}{d}}_{i=1}[gcd(i, \frac{n}{d})=1]\cdot i$$ (详见最小公倍数之和V3) 引用升级版题解中的引理： $$\sum^{n}_{i=1}i\cdot [gcd(i,n)=1]=\frac{n\cdot\phi(n)}{2}$$ 然后变成了：$$n\cdot \sum_{d|n}\frac{d\cdot \phi(d)}{2}$$ 我们就可以$O(n)$预处理$O(\sqrt{n})$查询了。 ``` #include<cstdio> #define LL long long using namespace std; const int maxn = 1e6 + 5; int pri[maxn], vis[maxn], t, n; LL ans, phi[maxn]; void MakePri(int n) { vis[1] = phi[1] = 1; for(register int i = 2; i <= n; ++i) { if(!vis[i]) pri[++pri[0]] = i, phi[i] = i - 1; for(register int j = 1; j <= pri[0] && i * pri[j] <= n; ++j) { vis[i * pri[j]] = 1; phi[i * pri[j]] = phi[i] * phi[pri[j]]; if(i % pri[j] == 0) { phi[i * pri[j]] = phi[i] * pri[j]; break; } } } } int main() { scanf("%d", &t); MakePri(1000000); register int i; while(t--) { scanf("%d", &n), ans = 1 + phi[n] * n / 2; for(i = 2; i * i <= n; ++i) if(n % i == 0) ans += phi[i] * i / 2 + phi[n / i] * (n / i) / 2; if((--i) * i == n) ans -= phi[i] * i / 2; printf("%lld\n", ans * n); } return 0; } ```
上一篇:
POJ2407 Relatives
下一篇:
VIJOS1655 萌萌的糖果博弈
0
赞
300 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册