603
技術社區[雲棲]
timus 1268 原根
題意：求K個素數pi對應的ni。ni滿足：ni，ni^2,ni^3,...,ni^m對pi取模各不相同(i=1,2,3,...)，且m最大，ni最大。
理論基礎： 原根的定義：首先，對於互質的兩個整數a，m。必然存在：d<=m-1，使得:a^d=1(mod m)，比如說:d=phi(m)。我們定義a對m的階為所有滿足a^d=1(mod m)的d中最小的一個正整數。如此一來，如果a對m的階為phi(m),那麼我們稱a為m一個原根。
原根性質定理：如果a為m的原根，記它的階為ord，那麼：a,a^2,a^3,...,a^ord對m取模的值各不相同。
定理1：對於整數a,與素數m，則a，a^m對m取模的結果相同(費馬小定理)。
定理2：可以證明，如果正整數（a,m）=1和正整數 d 滿足a^d=1(mod m)，則ord整除d。
定理：如果p為素數，那麼素數p一定存在原根，並且p的原根的個數為phi(p-1).
設m是正整數，a是整數，若a模m的階等於φ(m)，則稱a為模m的一個原根.
假設一個數g對於P來說是原根，那麼g^i mod P的結果兩兩不同,且有 1<g<P, 0<i<P,那麼g可以稱為是P的一個原根,歸根到底就是g^(P-1) = 1 (mod P)當且
僅當指數為P-1的時候成立.(這裏P是素數).
求原根目前的做法隻能是從2開始枚舉，然後暴力判斷g^(P-1) = 1 (mod P)是否當且當指數為P-1的時候成立。而由於原根一般都不大，所以可以暴力得到.
求一個奇素數的所有原根方法。
設g是P的平方非剩餘，是P-1的標準分解式，若恒有
成立，
則g就是P的原根。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 70000
bool isprime[maxn];
int prime[maxn],nprime;
void getprime()
{
long long i,j;
memset(isprime,1,sizeof(isprime));
nprime=0;
for(i=2; i<maxn; i++)
if(isprime[i])
{
prime[nprime++]=i;
for(j=i*i; j<maxn; j+=i)isprime[j]=0;
}
}
long long exp_mod(long long a,long long b,long long c)
{
a%=c;
long long ans=1;
while(b)
{
if(b&1)ans=ans*a%c;
b>>=1,a=a*a%c;
}
return ans;
}
bool judge(int yl,int n)
{
int x=n-1;
for(int i=0; prime[i]<=x; i++)
if(x%prime[i]==0)
if(exp_mod(yl,x/prime[i],n)==1)
return 0;
return 1;
}
int main()
{
int t,n;
getprime();
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=n-1; i>0; i--)
if(judge(i,n))
{
printf("%d\n",i);
break;
}
}
return 0;
}
最後更新：2017-04-03 15:22:13