poj 3614 伪素数问题

题意：1.p不是素数 2.(a^p)%p=a 输出yes  不满足输出no

思路：

1. 判断素数问题，直接暴力判断

bool is_prime(int n)

{  for(int i=2;i*i<=n;i++)    if(n%i==0) return false; 

    return n!=1;}

          2.(a^p)%p快速幂     注意大数快速幂要传入 long long 形参

解决问题的代码：

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
bool is_prime(int n)
{
        for (int i = 2; i*i <= n; i++)
               if (n%i == 0)    //说明不是素数
                       return false;
        return n != 1;  //忘记判断1
}
ll mod_p(ll a, ll b, ll c)  //形参为long long 型不然wa
{
        ll ans = 1ll;
        a %= c;
        while (b)
        {
               if (b & 1)
                       ans = (ans*a) % c;
               a = (a*a) % c;
               b >>= 1;
        }
        return ans;
}
int main()
{
        int p, a;
        while (scanf("%d%d", &p, &a) != EOF)
        {
               if (p == 0 && a == 0) break;
               if (!is_prime(p) && (mod_p(a, p, p) == a)) printf("yes
");
               else printf("no
");
        }
        return 0;
}