cf1208G Polygons 欧拉函数（思维好题）

题目大意

给你两个正整数和，询问在一个圆上你最少需要几个点构才能造出个边数小于等于的正多边形

思路

总的来说，这是一个思维好题。
深受迫害，所以写的详细一点，不会请留言。

性质1

考虑加进一个边形。那么他的因子一定在他之前加进来了.
因为可以完全由的点表现出来。
如果没加，那么加显然比加优秀(显然)。

性质2

两个图形，让他们尽量多的重合些点是好的。
那两个图形能重合多少点呢？答案显然是固定的。
两个图形让他们一个点重合，即可得到最好的。
因为是正多边形，所以随便重合一个点，重合的情况都是一样的。
即最优的答案。
所以我们加入的个正多边形都重合到一个点上，设这个点为点。

联系起来

在圆上,假设他的点为
由可以知道，0这个点上每个图形都会经过。
由可以知道的点上，他的因子在之前就会加入，所以他的因子及其倍数都是原先就有的(被覆盖过)。
这个过程就是类似于暴力筛的过程，所以剩下的就是与他互质的数。
所以一个正边形的贡献就是.
找出个最小的就行了
其实这个题就是俄罗斯数学竞赛的题目....我同桌给我讲过类似的证明，忘记了(菜)。

代码

因为1,2不是正x边形，所以不能选为k变形

#include <bits/stdc++.h>
using namespace std;
const int _=1e6+7,limit=1e6;
int phi[_];
void Euler() {
    for(int i=1;i<=limit;++i) phi[i]=i;
    for(int i=2;i<=limit;++i) {
        if(phi[i]==i) {
            phi[i]=i-1;
            for(int j=i+i;j<=limit;j+=i)
                phi[j]=(phi[j]/i)*(i-1);
        }
    }
}
std::vector<int> ans;
int main() {
    Euler();
    int n,k;
    cin>>n>>k;
    if(k==1) return puts("3"),0;
    for(int i=3;i<=n;++i) ans.push_back(phi[i]);
    sort(ans.begin(),ans.end());
    long long tot=0;
    for(int i=0;i<k;++i) tot+=ans[i];
    cout<<tot+2<<"\n";
    return 0;
}