欧拉函数为什么是偶数,欧拉函数数论

Problem - E - Codeforces

题意

思路

对于 k 次操作gcd(u, v) k 1代价的贡献就是二元组 (u, v)的个数 * (k 1)

那么就要我们求二元组个数

这个是个很经典的欧拉函数的套路可以用线性筛把欧拉函数求出来然后求个前缀和 s[i] 就是

1 ~ i 的所有数中 (u, v)满足 gcd(u, v) 1的二元组个数

容易发现操作从k大到小的代价一定是最小的

那么去算贡献即可

#include <bits/stdc.h>#define int long longconstexpr int N  1e6  10;constexpr int mod  998244353;constexpr int Inf  0x3f3f3f3f;int n, m;int len  0;int phi[N];int s[N];int prime[N], vis[N];void P_init(int n) {phi[1]  0;for (int i  2; i < n; i ) {if (!vis[i]) prime[len]  i, phi[i]  i - 1;for (int j  1; i < n / prime[j]; j ) {vis[i * prime[j]]  1;if (i % prime[j]  0) {phi[i * prime[j]]  phi[i] * prime[j];break;}else {phi[i * prime[j]]  phi[i] * phi[prime[j]];}}}for (int i  1; i < 1e6; i ) s[i]  s[i - 1]  phi[i];}void solve() {std::cin >> n >> m;int ans  0;for (int k  n - 1; k > 1; k --) {int d  std::min(s[n / (k  1)] / k, m / k);m - d * k;ans  d * (k  1);}if (m) {std::cout << -1 << \n;}else {std::cout << ans << \n;}}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t  1;P_init(1e6);std::cin >> t;while (t--) {solve();}return 0;}

Code