呃呃呃，大水题
首先有一个简单的贪心策略：先加边权大的边，然后再加边权小的边。容易证明她是正确的。
然后问题变为对于每一个 计算有多少个整数对 满足 且 了。考虑 dp。设 表示 时上式的答案，则显然有 。但是这显然是错的，因为 有可能被错误的统计在 内。考虑容斥。将所有 的倍数且不为 的数的贡献在 中减去。因此有：
直接暴力计算 的值是调和级数的，因此这样就能在单组数据 的时间复杂度内通过该题目。
代码：
#include <bits/stdc++.h>
#define eb emplace_back
#define int long long
using namespace std;
const int N = 1000100;
int f[N];
signed main() {
int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
for (int i = n; i; --i) {
f[i] = (n / i) * (n / i);
for (int j = 2; j * i <= n; ++j) {
f[i] -= f[j * i];
}
}
int sum = 0, cnt = 0;
for (int i = n; i > 1; --i) {
int k = min(m, f[i] / 2) / (i - 1) * (i - 1);
m -= k;
sum += k / (i - 1) * i;
}
if (m) {
sum = -1;
}
cout << sum << '\n';
}
return 0;
}
喜欢的话，留下你的评论吧～