【51nod1040】【最大公约数之和】【欧拉函数】
题目大意给出一个n，求1-n这n个数，同n的最大公约数的和。比如：n = 61,2,3,4,5,6 同6的最大公约数分别为1,2,3,2,1,6，加在一起 = 15解题思路 ans=∑x|nx∗∑ni=1gcd(i,n)==x => ans=∑x|nx∗∑ni=1gcd(i/...
51nod 1237 最大公约数之和 V3（杜教筛）
【题目链接】https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1237【题目大意】求[1,n][1,n]最大公约数之和【题解】枚举最大公约数k，得到答案为2*∑(k*phi_sum(n/k))-n*(n+1)/2phi_su...
51NOD 1237 最大公约数之和 V3 [杜教筛]
1237 最大公约数之和 V3题意：求\(\sum_{i=1}^n\sum_{j=1}^n(i,j)\)令\(A(n)=\sum_{i=1}^n(n,i) = \sum_{d\mid n}d \cdot \varphi(\frac{n}{d})\)\(ans = 2*\sum_{i=1}^n A(i...
51nod 237 最大公约数之和 V3 杜教筛
Code:#include <bits/stdc++.h>#include <tr1/unordered_map>#define setIO(s) freopen(s".in","r",stdin)#define ll long long#define ull unsigne...
UVa11426 最大公约数之和(正版)
题面求\(\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}gcd(i, j)\)n<=4000000,数据组数T<=100答案保证在64位带符号整数范围内（long long就好）Sol之前做了一道假的先不管i，j是否有序，我们就求\(\sum_{i=1}^{n}\sum...