codeforces 1243C 裴蜀定理_裴蜀定理 codeforces

分析

对于一个n，我们有1~n个位置，现在我们选两个位置$i,j$，若$|i-j|>1$且$|i-j|\mid n$那么i和j位置是一种颜色，问最多需要多少种颜色可以涂遍1~n
我们可以知道，n除了1以外的最小约数x，那么最多也就会有x种颜色
我们假设y为n的另一约数，且$\gcd (x,y)=1$
假设t位置仅由x,y贡献，有：$ax+by=t$
由裴蜀定理可以知道：t最小为$\gcd (x,y)=1$
所以n个位置都可以用一种颜色

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int main()
{
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    if(n == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    ll ans = n;
    vector <ll> pre;
    for(ll i = 2; i * i <= n; i ++)
    {
        if(n % i == 0)
        {
            pre.push_back(i);
            while(n % i == 0)
                n /= i;
        }
    }
    if(n > 1)
        pre.push_back(n);
    if(pre.size() == 1)
        cout << pre[0] << endl;
    else 
        cout << 1 << endl;
    //system("pause");
}
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