test/yuki3030.test.cpp

View this file on GitHub
Last update: 2021-06-21 15:24:20+09:00
Problem: https://yukicoder.me/problems/no/3030

Depends on

math/miller_rabin.cpp

Code

#define PROBLEM "https://yukicoder.me/problems/no/3030"
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 2;
#include "../math/miller_rabin.cpp"

int main() {
    ll n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        ull k; scanf("%lld", &k);
        printf("%lld %d\n", k, miller_rabin(k));
    }
    return 0;
}

#line 1 "test/yuki3030.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/3030"
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 2;
#line 1 "math/miller_rabin.cpp"
template< class T>
T pow_ (T x, uint64_t n, uint64_t M){
    T u = 1;
    if(n > 0){
        u = pow_(x, n/2, M);
        if (n % 2 == 0) u = (u*u) % M;
        else u = (((u * u)% M) * x) % M;
    }
    return u;
};

bool suspect(__uint128_t a, uint64_t s, uint64_t d, uint64_t n){
    __uint128_t x = pow_(a, d, n);
    if (x == 1) return true;
    for (int r = 0; r < s; ++r) {
        if(x == n-1) return true;
        x = x * x % n;
    }
    return false;
}

template<class T>
bool miller_rabin(T m){
    uint64_t n = m;
    if (n <= 1 || (n > 2 && n % 2 == 0)) return false;
    uint64_t d = n - 1, s = 0;
    while (!(d&1)) {++s; d >>= 1;}
    vector<uint64_t> v = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    if(n < 4759123141LL) v = {2, 7, 61};
    for (auto &&p : v) {
        if(p >= n) break;
        if(!suspect(p, s, d, n)) return false;
    }
    return true;
}
#line 18 "test/yuki3030.test.cpp"

int main() {
    ll n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        ull k; scanf("%lld", &k);
        printf("%lld %d\n", k, miller_rabin(k));
    }
    return 0;
}