SPOJ PROOT Primitive Root （数学找规律）

电玩女神 2022-06-04 03:57 186阅读 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.

### Example ###

Input:
    5 2
    3
    4
    
    7 2
    3
    4
    
    0 0
    
    
    Output:
    YES
    NO
    YES
    NO

### Explanation ###

In the first test case 31, 32 , 33 and 34 are respectively 3, 4, 2 and 1 (mod 5). So, 3 is a primitive root of 5.

41, 42 , 43 and 44 are respectively 4, 1, 4 and 1 respectively. So, 4 is not a primitive root of 5.

题解：

给一个n，m,m组数据，每组数据的k，表示一个数字，表示以k为底，下标从1到n-1，数值mod n如果不重复，就输出yes，否则no

思路：

打表出所有n-1的因子，假设当前因子之一有个x，看k的x次方mod n是否为1，为1就是no，遍历完还没找到1就是yes

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    ll quick(ll x,ll y,ll m)
    {
        int ans=1;
        while(y!=0)
        {
            if(y%2==1)
            {
                ans=(ans*x)%m;
            }
            x=(x*x)%m;
            y/=2;
        }
        return ans;
    }
    int ans;
    int p[1005];
    int main()
    {
        ll i,j,n,m,d;
        while(scanf("%lld%lld",&n,&m)!=EOF)
        {
            if(n==0&&m==0)
                break;
            ans=0;
            ll t=n-1;
            ll temp=sqrt(t);
            for(i=2;i<=temp;i++)
            {
                if(t%i==0)
                {
                    ll s=t/i;
                    if(s==i)
                    {
                        p[ans]=i;
                        ans++;
                    }
                    else
                    {
                        p[ans]=i;
                        p[ans+1]=s;
                        ans+=2;
                    }
                }
            }
            while(m--)
            {
                int tag=1;
                scanf("%lld",&d);
                for(i=0;i<ans;i++)
                {
                    if(t%p[i]==0)
                    {
                        if(quick(d,p[i],n)==1)
                        {
                            tag=0;
                            goto loop;
                        }
                    }
                }
                loop:;
                if(tag)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        }
        return 0;
    }