SPOJ PROOT Primitive Root （数学找规律）-蒲公英云

SPOJ PROOT Primitive Root （数学找规律）

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