题解：CF1731E Graph Cost

· · 题解

首先有一个结论，能选大的 k 就尽量选大的。

证明：我们要使花费代价最小，然而添加的边数是固定的，即，我们要让添加的平均代价最小。那么如果选 k 条边，平均每条边的代价为 \dfrac{k+1}{k}。如果选 k+1 条边，平均每条边的代价为 \dfrac{k+2}{k+1}，通分得 \dfrac{k^2+2k+1}{k^2+k}>\dfrac{k^2+2k}{k^2+k}。显然后者代价更小。故得证。

那么我们就从 n 开始枚举 k，对于每一个枚举到的 k，我们怎么判断有没有 k+1 对点能满足 \gcd(u,v)=k+1 呢？

最大公约数有一个性质：若 \gcd(u,v)=g，则 \frac{u}{g}\bot\frac{v}{g}。证明显然，这里不提。

那么我们判断最大公约数就可以转化为：从 1 到 \frac{n}{k+1} 中有没有 k+1 对数互质。

也就是要解决这样一个问题：求 [1,p] 中的互质数组数。

怎么解决？暴力枚举+根号枚举判断？太慢了，是 O(n^2\sqrt n) 的。

有互质，可以往欧拉函数上面想。根据欧拉函数的定义，有 \phi(n)=\sum\limits_{i=1}^nn\bot i。就是说， \phi(n) 为 [1,n] 中，与 n 互质的数的个数。

这个定义很优美。为什么这么说？可以想到，其前缀和 sum=\sum\limits_{i=1}^n\phi(i) 的值不就是 [1,n] 中，互质数的组数吗？

求 [1,n] 欧拉函数及其前缀和的方法是线性筛，其可以做到 O(n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+10;
int phi[N],sum[N],Prime[N],cnt;
bool vis[N];
void Getphi(){
    phi[1] = 1;
    for(int i = 2;i<N;i++){
        if(!vis[i]){
            vis[i] = i;
            Prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j<=cnt;j++){
            if(i*Prime[j] > N) break;
            vis[i*Prime[j]] = Prime[j];
            if(i%Prime[j] == 0){
                phi[i*Prime[j]] = phi[i]*Prime[j];
                break;
            }
            phi[i*Prime[j]] = phi[i]*phi[Prime[j]];
        }
        sum[i] = sum[i-1] + phi[i];
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T; cin>>T;
    Getphi();
    while(T--){
        int n,m,ans = 0;
        cin>>n>>m;
        for(int k = n;k>=1;k--){
            int maxn = min(sum[n/(k+1)],m)/k;
            ans += maxn * (k+1);
            m -= maxn * k;
        }
        cout<<(m > 0 ? -1 : ans)<<'\n';
    }
    return 0;
}