poj 3641:擬似素数検出

miller robin素数テストの偽素数定義を知っていれば簡単に解決できるので、詳しくはまとめを参照してください.

#include <iostream>

#include<stdio.h>

#include<algorithm>

#include<time.h>

#include<math.h>

using namespace std;

long long n;long long multi(long long a,long long b,long long m)//a*b%m

{

    long long res=0;

    while(b>0)

    {

        if(b&1)

            res=(res+a)%m;

        b>>=1;

        a=(a<<1)%m;

    }

    return res;

}

long long quickmod(long long a,long long b,long long m) //a^b%m

{

    long long res=1;

    while(b)

    {

        if(b&1)

            res=multi(res,a,m);

        b>>=1;

        a=multi(a,a,m);

    }

    return res;

}

bool isprime(long long n)

{

    for(int i=2;i*i<=n;i++)

    {

        if(!(n%i))

            return 0;

    }

    return 1;

}int main()

{

    long long p,a;

    while(scanf("%I64d%I64d",&p,&a),p+a)

    {

        if(isprime(p))

        {

            puts("no");

            continue;

        }

        if(quickmod(a,p,p)==a)

            puts("yes");

        else

            puts("no");

    }

    return 0;

}