結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー lyulu
提出日時 2021-12-05 17:35:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,737 bytes
コンパイル時間 1,221 ms
コンパイル使用メモリ 100,028 KB
最終ジャッジ日時 2025-01-26 05:16:00
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 TLE * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <math.h>
#include <iostream>
#include <numeric>
#include <vector>


// C++17で動作
namespace myAKS {
    // 配列形式で多項式を表す
    class polynomial_modulo {
        private:
            long long n, r, a;
            std::vector<long long> ls1, ls2;
            void set_ls1() {
                // x^n + a = x^(n-r) * (x^r-1) + (x^(n-r) + a) ...
                ls1[0] = a % n;
                ls1[n%r] = (++ls1[n%r]) % n;
            }
            void set_ls2() {
                // a * x^n = a * x^(n%r) (mod x^r - 1)
                std::vector<long long> tmp(r, 0);
                ls2[0] = 1;
                tmp[1] = 1; tmp[0] = a;  // x + a
                int n_ = n;
                while(n_ > 0) {
                    if(n_ & 1) {
                        ls2 = mul(ls2, tmp);
                    }
                    tmp = mul(tmp, tmp);
                    n_ >>= 1;
                }
            }
            std::vector<long long> mul(std::vector<long long> lhs, std::vector<long long> rhs) {
                std::vector<long long> retval(r, 0);
                // FFT ?
                for(long long i = 0; i < r; ++i) {
                    for(long long j = 0; j < r; ++j) {
                        retval[(i+j)%r] += lhs[i] * rhs[j] % n;
                        retval[(i+j)%r] %= n;
                    }
                }
                return retval;
            }
        public:
            polynomial_modulo(long long n_, long long r_, long long a_) {
                n = n_; r = r_; a = a_;
                ls1.resize(r, 0);  // x^n + a
                ls2.resize(r, 0);  // (x + a)^n
                set_ls1();
                set_ls2();
            }
            bool is_same() {
                for(long long i = 0; i < r; ++i) {
                    if(ls1[i] != ls2[i]) {
                        return false;
                    }
                }
                return true;
            }
    };

    // floor(log2(x)) の計算
    // 制約: n >= 1
    int floor_log2(long long n) {
        int log2_n = 0;
        n >>= 1;
        while(n > 0) {
            n >>= 1;
            ++log2_n;
        }
        return log2_n;
    }

    // 整数の累乗計算
    // 制約: k >= 0, 64bit整数の範囲に収まる入力
    long long powint(long long n, int k) {
        long long tmp = n, retval = 1;
        while(k > 0) {
            if(k & 1) {
                retval *= tmp;
            }
            tmp *= tmp;
            k >>= 1;
        }
        return retval;
    }

    // 累乗数の判定
    // 制約: n >= 2
    bool is_perfect_power(long long n) {
        for(int i = 2; i <= floor_log2(n); ++i) {
            int root = roundl(pow(n, 1.0L / i));
            if(powint(root, i) == n) {
                return true;
            }
        }
        return false;
    }

    // 位数の計算
    // 制約: n >= 0, mod >= 1
    long long order(long long n, long long mod) {
        long long mul = 1;
        for(long long e = 1; e < mod; ++e) {
            mul *= n;
            mul %= mod;
            if(mul == 1) {
                return e;
            }
        }
        return -1;
    }

    // 位数に関する不等式を満たすような最小の数を算出
    // 制約: n >= 1
    long long enough_order_modulo(long long n) {
        long long rhs = floorl(log2((long double)n) * log2((long double)n));
        for(long long r = 1; r < n; ++r) {
            if(order(n, r) > rhs) {
                return r;
            }
        }
        return n;
    }

    // 素因数列挙
    // 制約: n >= 1
    std::vector<long long> primefactors(long long n) {
        long long tmp = n;
        std::vector<long long> retval;
        for(long long i = 2; i*i <= n; ++i) {
            while(tmp % i == 0) {
                tmp /= i;
                retval.emplace_back(i);
            }
        }
        if(tmp > 1) {
            retval.emplace_back(tmp);
        }
        return retval;
    }

    // オイラーのトーシェント関数
    // 制約: nは32bit整数の範囲(でないと計算時に64bit整数に収まらない可能性が出てくる)
    long long totient(long long n) {
        std::vector<long long> pfs = primefactors(n);
        long long retval = n;
        for(long long pf: pfs) {
            retval *= (pf-1);
            retval /= pf;
        }
        return retval;
    }

    // AKSアルゴリズムによる素数判定
    // 制約: n <= 2^31 (0 以下の整数は false, mod n の乗算が厳しい)
    bool is_prime(long long n) {
        // 1(と0以下の整数)は素数でない
        if(n <= 1) {
            return false;
        }

        // Step1
        if(is_perfect_power(n)) {
            return false;
        }

        // Step2
        long long r = enough_order_modulo(n);

        // Step3
        for(long long a = 2; a <= std::min(r, n-1); ++a) {
            long long gcd_an = std::gcd(a, n);
            if(1 < gcd_an && gcd_an < n) {
                return false;
            }
        }

        // Step4
        if(n <= r) {
            return true;
        }

        // Step5
        long long rangemax = floorl(sqrt((long double)totient(r)) * log2l((long double)n));
        for(long long a = 1; a <= rangemax; ++a) {
            polynomial_modulo pm(n, r, a);
            if(!pm.is_same()) {
                return false;
            }
        }

        // Step6
        return true;
    }
}  // namespace myAKS


int main() {
    long long n, a;
    std::cin >> n;
    for(int i = 0; i < n; ++i) {
        std::cin >> a;
        bool is_prime = myAKS::is_prime(a);
        if(is_prime) std::cout << a << " 1\n";
        else std::cout << a << " 0\n";
    }
}
0