【杭电1905】Pseudoprime numbers

比眉伴天荒 2022-09-24 03:28 144阅读 0赞

![这里写图片描述][20160723153020188]  
![这里写图片描述][20160723153030237]  
伪素数，只要看懂题别把素数算进来算就ok

#include<stdio.h>
    #include<math.h>
    __int64 quickpow(int n,int m,int t) {
        __int64 ans=1,base=n;
        while(m) {
            if(m&1) {
                ans=ans*base%t;
            }
            base=base*base%t;
            m>>=1;
        }
        return ans;
    }
    bool judge(int p) {
        for(int l=2; l<=sqrt(p); l++) {
            if(p%l==0)
                return true;
        }
        return false;
    }
    int main() {
        int p,a;
        while(scanf("%d %d",&p,&a),p||a) {
            __int64 t;
            if(judge(p)) {
                t=quickpow(a,p,p);
                if(t==a)
                    printf("yes\n");
                else
                    printf("no\n");
            } else
                printf("no\n");
        }
        return 0;
    }

[http://acm.hdu.edu.cn/showproblem.php?pid=1905][http_acm.hdu.edu.cn_showproblem.php_pid_1905]

[20160723153020188]: /images/20220720/21e9895b8c2d4ac9a03fb5da69833d11.png
[20160723153030237]: /images/20220720/f53c017fef1a4848a0a08513cda84cce.png
[http_acm.hdu.edu.cn_showproblem.php_pid_1905]: http://acm.hdu.edu.cn/showproblem.php?pid=1905

发表评论取消回复

表情：

评论列表（有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 3641 Pseudoprime numbers（快速幂）

嗯... 题目链接：http://poj.org/problem?id=3641 AC代码： ![ContractedBlock.gif][] ![Expan

r囧r小猫/ 2023年06月04日 13:58/ 0 赞/ 16 阅读

相关【杭电oj1711】Number Sequence

Number Sequence Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (

待我称王封你为后i/ 2022年09月25日 06:28/ 0 赞/ 177 阅读

相关【杭电1905】Pseudoprime numbers

![这里写图片描述][20160723153020188] ![这里写图片描述][20160723153030237] 伪素数，只要看懂题别把素数算进来算就ok

比眉伴天荒/ 2022年09月24日 03:28/ 0 赞/ 145 阅读

相关杭电1005-Number Sequence

Number Sequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (J

小鱼儿/ 2022年08月08日 14:53/ 0 赞/ 127 阅读

相关杭电1018-Big Number（大数）

Big Number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

淡淡的烟草味﹌/ 2022年08月04日 10:46/ 0 赞/ 154 阅读

相关杭电1212 Big Number (大数求模运算)

Big Number Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/O

拼搏现实的明天。/ 2022年08月01日 06:10/ 0 赞/ 185 阅读

相关 POJ 3641 Pseudoprime numbers （快速幂）

> Pseudoprime numbers > Time Limit: 1000MS Memory Limit: 65536K > Total Submissions:

一时失言乱红尘/ 2022年07月03日 15:26/ 0 赞/ 126 阅读

相关 POJ 3641 Pseudoprime numbers

Pseudoprime numbers <table> <tbody> <tr> <td><strong>Time Limit:</strong>&

ゝ一纸荒年。/ 2022年06月01日 07:49/ 0 赞/ 145 阅读

相关 Pseudoprime numbers POJ - 3641(快速幂)

Fermat's theorem states that for any prime number p and for any integer a > 1, ap = a (m

喜欢ヅ旅行/ 2022年02月20日 16:19/ 0 赞/ 186 阅读

相关杭电acm_1005Number Sequence

[http://acm.hdu.edu.cn/showproblem.php?pid=1005][http_acm.hdu.edu.cn_showproblem.php_pid

缺乏、安全感/ 2021年12月13日 03:45/ 0 赞/ 282 阅读