题解：CF1208G Polygons

· · 题解

思路

对其他题解的补充。可以配合食用。

很巧妙的题目。拿到题显然考虑类似于反悔贪心的思路：先从小到大加，如果出现不优的方案就进行替换来寻找规律。

那么容易发现对于 x 边形，x 的因子（不包括 x，1，2）来说，它们一定是可以在 x 边形里面画出来的。又有一个性质 \sum_{x|y} \phi(x) = y ，所以我们可以根据这个东西来处理在从 1 到 n 挨着加时候的去重部分。对于 i 边形而言，它的因子的 \phi 都已经算过了，对于它就只用算 \phi(i) 了。这就是为什么 i 的贡献是 \phi(i)。

回到题目本身。既然跟 \phi 有关就线性筛先处理出所有 1 到 n 中的 \phi 值。按这个从小到大排序。发现一个性质：如果选择了 x 的倍数，一定选了 x，因为 \phi (xi) \ge \phi(x)，所以 x 肯定在之前就被选择了。

那么我们取前 k 个一定满足题目，因为算贡献的时候肯定是把每一个都算进去了，可以用上面的性质证明。

在特判的时候考虑 k \le 2 的情况即可，就是三角形和四边形。

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,k,len,ans,pri[1000010],phi[1000010];
bool vis[1000010];
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            pri[++len]=i;
            phi[i]=i-1;
        }
        for(int j=1;i*pri[j]<=n;j++){
            vis[i*pri[j]]=true;
            if(i%pri[j]) phi[i*pri[j]]=phi[i]*(pri[j]-1);
            else{
                phi[i*pri[j]]=phi[i]*pri[j];
                break; 
            }
        }
    }
    sort(phi+1,phi+1+n);
    for(int i=3;i<=k+2;i++) ans+=phi[i];
    cout<<ans+1+(k!=1);
    return 0;
}