SPOJ - PROOT(数论+原根)

小灰灰 2022-06-04 05:17 204阅读 0赞

问题描述:

In the field of Cryptography, prime numbers play an important role. We are interested in a scheme called "Diffie-Hellman" key exchange which allows two communicating parties to exchange a secret key. This method requires a prime number p and r which is a primitive root of p to be publicly known. For a prime number p, r is a primitive root if and only if it's exponents r, r2, r3, ... , rp-1 are distinct (mod p).

Cryptography Experts Group (CEG) is trying to develop such a system. They want to have a list of prime numbers and their primitive roots. You are going to write a program to help them. Given a prime number p and another integer r < p , you need to tell whether r is a primitive root of p.

### Input ###

There will be multiple test cases. Each test case starts with two integers p ( p < 2 31 ) and n (1 ≤ n ≤ 100 ) separated by a space on a single line. p is the prime number we want to use and n is the number of candidates we need to check. Then n lines follow each containing a single integer to check. An empty line follows each test case and the end of test cases is indicated by p=0 and n=0 and it should not be processed. The number of test cases is atmost 60.

### Output ###

For each test case print "YES" (quotes for clarity) if r is a primitive root of p and "NO" (again quotes for clarity) otherwise.

Input:
    5 2
    3
    4
    
    7 2
    3
    4
    
    0 0

题目题意:判断一个数是否为给定素数的原根。

题目分析:我们把p-1的因子全部打出来，然后去根据原根的性质判断一下，如果在p-1之前出现了a^x %p=1（x为p-1的因子）那么就不是

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #define ll long long
    using namespace std;
    
    const int maxn=1e3+100;
    int factor[maxn],fcnt;
    
    void get_factor(int n)
    {
        fcnt=0;
        for (int i=1;i<=(int)sqrt(n);i++) {
            if (n%i==0) {
                if (i*i==n) {
                    factor[fcnt++]=i;
                }
                else {
                    factor[fcnt++]=i;
                    factor[fcnt++]=n/i;
                }
            }
        }
        sort (factor,factor+fcnt);
    }
    ll fast_pow(ll base,ll k,ll mod)
    {
        ll ans=1;
        while (k) {
            if (k&1)
                ans=ans*base%mod;
            base=base*base%mod;
            k>>=1;
        }
        return ans%mod;
    }
    int main()
    {
        int p,n;
        while (scanf("%d%d",&p,&n)!=EOF) {
            if (p==0&&n==0) break;
            get_factor(p-1);
            for (int i=1;i<=n;i++) {
                int a;
                scanf("%d",&a);
                bool flag=true;
                for (int i=0;i<fcnt-1;i++) {
                    if (fast_pow(a,factor[i],p)==1) {
                        flag=false;
                        break;
                    }
                }
                if (flag) puts("YES");
                else puts("NO");
            }
        }
        return 0;
    }