题目传送门:D-月月给华华出题_牛客小白月赛12 (nowcoder.com)
思路 / Thought
如果按照朴素的想法,对于每一个N,用 i 遍历1~N,每一个i又用O(i)的复杂度算出ans[i],复杂度大概是O(N ^ 2 * logN),显然不行,应该找到数字之间的规律。
对于每一个数字x的所有因子d,有可能是x与某个i的最大公因数,于是我们可以改变一个角度,从因子d的角度去思考,如果gcd(i, x) == d,那么就要加上i / d,否则就不加。
再经过一系列的推导,可以得到最后的公式。

关于最后一步欧拉函数性质的解释:如果gcd(d, n) = 1,那么有gcd(d, n - d) = 1(欧几里得算法),意思是[1, n-1]中与n互质的数字都是成对出现的且每一对和为n,那么也就是平均每个数字都是n / 2。
代码 / Code
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 9; int phi[maxn]; void init(int n) { for(int i = 1;i <= n; ++ i)phi[i] = i; for(int i = 2;i <= n; ++ i) if(phi[i] == i)for(int j = i;j <= n; j += i)phi[j] = phi[j] / i * (i - 1); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int N;cin >> N; init(N); vector<int> ans(N + 1, 0); for(int i = 1;i <= N; ++ i)//i是因子 for(int j = i;j <= N; j += i)ans[j] += phi[i] * i / 2; for(int i = 1;i <= N; ++ i)cout << ans[i] + 1 << '\n'; return 0; }
Comments NOTHING