首页 > 代码库 > hdu 1905 幂成

hdu 1905 幂成

2024-07-02 04:02:40   219人阅读

题意：//给一个p 和一个a，如果这个
//p 本身就是一个素数，就输出no，如果不是素数，那么计算 ( a ^ p) % p 如果结果等于a 那么输出yes 否则输出no

zsd:用__int64的时候一定要注意__int64与别的数转化的时候会出错误 所以一定要都是__int64位

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//给一个p 和一个a，如果这个
//p 本身就是一个素数，就输出no，如果不是素数，那么计算 ( a ^ p) % p 如果结果等于a 那么输出yes 否则输出no
#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int x)
{
    for(int i=2;i<=(int)sqrt(x*1.0)+1;i++)
        if(x%i==0)
            return false;
    return  true;
}
bool fun(__int64 x,__int64 e,__int64 p)
{
    __int64 a=x;
    __int64 base=x;
    __int64 sum=1;
    while(e>0)
    {
        if(e&1) sum=(sum*base)%p;
        e/=2;
        base=(base*base)%p;
    }
    if(sum==a)
        return true;
    return false;
}
int main()
{
    __int64 p,a;
    while(scanf("%I64d%I64d",&p,&a)!=EOF)
    {
        if(p==a&&p==0) break;
        if(isprime(p)) printf("no\n");
        else
            if(fun(a,p,p))
                printf("yes\n");
            else printf("no\n");
    }
    return 0;
}

 


联系
我们