Kattis - pseudoprime 【快速幂】

题意

给出两个数字 P 和 A 当p 不是素数并且满足a^p≡a(mod p) 就输出 yes 否则输出 no

思路

因为数据范围较大，用快速幂

AC代码

#include <cstdio>

#include <cstring>

#include <ctype.h>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <map>

#include <stack>

#include <set>

#include <numeric>

#include <sstream>

using namespace std;

typedef long long LL;

const double PI  = 3.14159265358979323846264338327;

const double E   = 2.718281828459;

const double eps = 1e-6;

const int MAXN = 0x3f3f3f3f;

const int MINN = 0xc0c0c0c0;

const int maxn = 1e5 + 5;

const int MOD  = 1e9 + 7;

LL powerMod(LL x, LL n, LL m)

{

    LL res = 1;

    while (n > 0)

    {

        if (n & 1)

            res = (res * x) % m;

        x = (x * x ) % m;

        n >>= 1;

    }

    return res;

}

bool isPrime(int x)

{

    int flag;

    int n, m;

    if (x <= 1)

        return false;

    if (x == 2 || x == 3)

        return true;

    if (x % 2 == 0)

        return false;

    else

    {

        m = sqrt(x) + 1;

        for (n = 3; n <= m; n += 2)

        {

            if (x % n == 0)

            {

                return false;

            }

        }

        return true;

    }

}

int main()

{

    LL p, a;

    while (cin >> p >> a && (p || a))

    {

        if (powerMod(a, p, p) == a && a % p == a && isPrime(p) == false)

            cout << "yes\n";

        else

            cout << "no\n";

    }

}

巴特西

Kattis - pseudoprime 【快速幂】

最新文章

热门文章