CF1208G Polygons

发表于 | 阅读数

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

假设我们已经构造出了$p$边形，实际上$k|p$也都构造出来了。增加多出来的点数即是$\phi (p)$。
或者这么理解会多出来的$\frac{1}{p}+\frac{2}{p}…\frac{p}{p}$个点，发现有些点可以约分。就是已经构造出来的点又$\phi (p)>\phi(k)$。就可以贪心得去选，因为选到$p$边形的时候前面$k$一定选过。

  • 都有公共顶点$\frac{p}{p},+1$
  • 二边形不存在，对于偶数边$+1$例如$\frac{2}{4},\frac{2}{6}$，$\phi(2,1)=1,\phi(3,4,6)=2$，需要构造$\geq4$,需要$+1$，特判$3$即可
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
int prime[N], notprime[N];
int cnt, phi[N];
void init()
{
    phi[1] = 1;
    for (int i = 2; i < N; i++)
    {
        if (!notprime[i])
        {
            prime[++cnt] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= cnt && i * prime[j] < N; j++)
        {
            notprime[i * prime[j]] = 1;
            if (i % prime[j])
                phi[i * prime[j]] = phi[prime[j]] * phi[i];
            else
            {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
        }
    }
}
vector<int> g;
ll ans = 0;
int n, k;
int main()
{
    init();
    scanf("%d%d", &n, &k);
    if (n == 3)
    {
        printf("3\n");
        return 0;
    }
    for (int i = 3; i <= n; i++)
        g.push_back(phi[i]);
    sort(g.begin(), g.end());
    for (int i = 0; i < k; i++)
        ans += g[i];
    printf("%lld", ans + 2);
}