【欧拉函数】CF1731E

我会带着你远行 2024-02-20 08:54 23阅读 0赞

[Problem - E - Codeforces][]

题意

![b42ceb99010c4d24a573e4007dc2736d.png][]

思路

对于 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 long
    
    constexpr 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：

[Problem - E - Codeforces]: https://codeforces.com/contest/1731/problem/E
[b42ceb99010c4d24a573e4007dc2736d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/78eac01687cf4a3fafa4543a21a122fb.png