[牛客小白月赛12]D.月月给华华出题（欧拉函数 + 数学）

题目传送门：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;
}