51nod1135——原根

題目連結：https://vjudge.net/contest/332708#problem/R

題目：

設m是正整數，a是整數，若a模m的階等于φ(m)，則稱a為模m的一個原根。（其中φ(m)表示m的歐拉函數）

給出1個質數P，找出P最小的原根。

Input

輸入1個質數P(3 <= P <= 10^9)

Output

輸出P最小的原根。

Sample Input

3      

Sample Output

2      

題解：

做這個題首先要知道原根的定義（不懂請參考這篇博文：原根）

前面的一大堆定義可以看也可以不看（如果不懂的話，比如我），我們隻需要記住一句話就行了。

如果g是P的原根，就是g^(P-1) = 1 (mod P)當且僅當指數為P-1的時候成立.(這裡P是素數)。

然後就是怎麼求解的問題了，政策有兩種：暴力枚舉和有規律的枚舉。

當然暴力枚舉的方法很簡單，我們隻需要從2開始，暴力枚舉g并判斷g^(P-1) = 1 (mod P)是否當且僅當指數為P-1的時候成立。

其實這樣速度也不慢，因為原根通常不大。

不過既然我們有優化版本的，我們肯定要用最好的，這裡我們需要知道裴蜀定理和歐拉定理，具體内容和證明參考上面給的博文。

我就直接講怎麼去求。

求一個質數的一個原根，先枚舉g。

然後我們可以求出x-1的所有質因子，然後去枚舉每個質因子p1,p2,p3...pn，判斷是否滿足g^((x-1)/pi)==1(mod p)。

若滿足則是原根，否則不是（證明請參考上面的連結）。

那麼我們這個題就可以先預處理求出範圍内所有的質因子，之後再枚舉g.

然後枚舉質因子判斷是否是g的質因子，之後就和上面的步驟一樣了。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#define rp(i, s, t) for (i = s; i <= t; i++)
#define RP(i, s, t) for (i = t; i >= s; i--)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
    int a = 0, b = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            b = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        a = (a << 3) + (a << 1) + c - '0';
        c = getchar();
    }
    return a * b;
}
inline void write(int n)
{
    if (n < 0)
    {
        putchar('-');
        n = -n;
    }
    if (n >= 10)
        write(n / 10);
    putchar(n % 10 + '0');
}
const int N = 1e5 + 7;
int prime[N];
bool visited[N];
int tot;
int p;
void init()//線性篩
{
    memset(visited, false, sizeof visited);
    tot = 0;
    int i, j;
    rp(i, 2, N - 1)
    {
        if (!visited[i])
        {
            prime[tot++] = i;
            visited[i] = true;
        }
        rp(j, 0, tot - 1)
        {
            if (i * prime[j] > N)
                break;
            visited[i * prime[j]] = true;
            if (i % prime[j] == 0)
                break;
        }
    }
}
ll quick_mod(ll a, ll b)//快速幂
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % p;
        b >>= 1;
        a = (a * a) % p;
    }
    return res;
}
bool judge(int x)
{
    int i;
    int pri[N];
    int prime_num = 0;
    int k = p - 1;
    rp(i, 0, tot - 1)//先求出k的所有質因子
    {
        if (k % prime[i] == 0)
        {
            pri[prime_num++] = prime[i];
            while (k % prime[i] == 0)
                k /= prime[i];
        }
        if (k == 1)
            break;
        if (k / prime[i] < prime[i])
        {
            pri[prime_num++] = prime[i];
            break;
        }
    }
    rp(i, 0, prime_num - 1)//枚舉質因子并判斷
    {
        if (quick_mod(x, (p - 1) / pri[i]) == 1)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    init();
    p = read();
    int i = 2;
    while (1)
    {
        if (judge(i))
            break;
        i++;
    }
    write(i);
    return 0;
}