原根（最小）

版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/46380515

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <math.h>

using namespace std;

const int MAXN = 100000;

int prime[MAXN+1];

void getPrime()
{
    memset(prime,0,sizeof(prime));
    for (int i = 2; i <= MAXN; i++)
    {
        if (!prime[i]) prime[++prime[0]] = i;
        for (int j = 1; j <= prime[0] && prime[j] <= MAXN / i; j++)
        {
            prime[prime[j] * i] = 1;
            if (i%prime[j] == 0) break;
        }
    }
}
long long factor[100][2];
int fatcnt;
int getFactor(long long x)
{
    fatcnt = 0;
    long long tmp = x;
    for (int i = 1; prime[i] <= tmp / prime[i]; i++)
    {
        factor[fatcnt][1] = 0;
        if (tmp%prime[i] == 0)
        {
            factor[fatcnt][0] = prime[i];
            while (tmp%prime[i] == 0)
            {
                factor[fatcnt][1]++;
                tmp /= prime[i];
            }
            fatcnt++;
        }
    }
    if (tmp != 1)
    {
        factor[fatcnt][0] = tmp;
        factor[fatcnt++][1] = 1;
    }
    return fatcnt;
}
long long pow_m(long long m, long long n, long long  k)
{
    long long  b = 1;
    while (n)
    {
        if (n & 1)
            b = (b*m) % k;
        n = n >> 1;
        m = (m*m) % k;
    }
    return b;
}

void solve(int p)
{
    if (p == 2)
    {
        printf("1\n");
        return;
    }
    getFactor(p-1);
    for (int g = 2; g < p; g++)
    {
        bool flag = true;
        for (int i = 0; i < fatcnt; i++)
        {
            int t = (p - 1) / factor[i][0];
            if (pow_m(g, t, p) == 1)
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            printf("%d\n",g);
            return;//若求所有原根去掉return即可。
        }
    }
}

int main()
{
    getPrime();
    int p;
    while (scanf("%d", &p)!=EOF)
    {
        solve(p);
    }
    return 0;
}

ACdreamer 对原根的详解： http://blog.csdn.net/acdreamers/article/details/8883285

百度百科：
http://baike.baidu.com/link?url=15SrOU2zwh6ZV1hYBI7QR9VrbSPpzXP0iUYWkLR9oWHJhWKmlI69ObQ1H_29FE19sXbpGUN9RHFVBaIz7jgfaa