1135 原根

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。（其中φ(m)表示m的欧拉函数）

给出1个质数P，找出P最小的原根。

Input

输入1个质数P(3 <= P <= 10^9)

Output

输出P最小的原根。

Input示例

Output示例

AC代码

就是找到最小的数x，使 $x^{\phi \left( n\right) }\% n=1$

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <limits.h>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <set>

#include <string>

#define ll long long

#define ull unsigned long long

#define ms(a) memset(a,0,sizeof(a))

#define pi acos(-1.0)

#define INF 0x7f7f7f7f

#define lson o<<1

#define rson o<<1|1

const double E=exp(1);

const int maxn=1e6+10;

const int mod=1e9+7;

using namespace std;

int p[maxn];

int k;

ll Pow(ll a,ll b,ll c)

{

	ll res=1;

	while(b)

	{

		if(b&1)

			res=res*a%c;

		b>>=1;

		a=a*a%c;

	}

	return res;

}

void getp(ll n)

{

	for(int i=2;i*i<=n;i++)

	{

		if(n%i==0)

		{

			p[k++]=i;

			while(n%i==0)

				n/=i;

		}

	}

	if(n>1)

		p[k++]=n;

}

int main(int argc, char const *argv[])

{

	ios::sync_with_stdio(false);

	ll n;

	cin>>n;

	k=0;

	// 素数的欧拉函数值为n-1

	// 对欧拉值进行分解

	getp(n-1);

	for(int i=2;i<n;i++)

	{

		int flag=0;

		for(int j=0;j<k;j++)

		{

			if(Pow(i,(n-1)/p[j],n)==1)

			{

				flag++;

				break;

			}

		}

		if(!flag)

		{

			cout<<i<<endl;

			return 0;

		}

	}

	return 0;

}

巴特西

51Nod 1135：元根（数论）

1135 原根

AC代码

最新文章

热门文章