結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー momoyuu
提出日時 2023-05-15 16:36:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 110 ms / 9,973 ms
コード長 3,698 bytes
コンパイル時間 3,265 ms
コンパイル使用メモリ 246,968 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-30 22:05:14
合計ジャッジ時間 4,756 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 998'244'353;
//const ll mod = 1'000'000'007;
//const ll mod = 67'280'421'310'721;
struct mint{
    long long x;
    mint(long long x=0):x((x%mod+mod)%mod){}
    mint operator-() const{
        return mint(-x);
    }
    mint& operator+=(const mint& a){
        if((x+=a.x)>=mod)x-=mod;
        return *this;
    }
    mint& operator-=(const mint& a){
        if((x+=mod-a.x)>=mod)x-=mod;
        return *this;
    }
    mint& operator*=(const  mint& a){
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint& a) const{
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const{
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const{
        mint res(*this);
        return res*=a;
    }
    mint pow(long long n) const {
        assert(0 <= n);
        mint a = *this, r = 1;
        while (n) {
            if (n & 1) r *= a;
            a *= a;
            n >>= 1;
        }
        return r;
    }
    mint inv() const{
        return pow(mod-2);
    }
    mint& operator/=(const mint& a){
        return (*this)*=a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res/=a;
    }
    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
    bool operator==(const mint& a) const {
        return x == a.x;
    }
    bool operator<(const mint& a) const{
        return x < a.x;
    }
};

ll calc(ll n,ll p){
    ll cnt = 0;
    while(n){
        cnt += n / p;
        n /= p;
    }
    return cnt;
}
const unsigned long long numset[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022ULL};
unsigned long long mod_mul(unsigned long long a, unsigned long long b, unsigned long long mod) {
long long ret = a * b - mod * (unsigned long long)((long double)(a) * (long double)(b) / (long double)(mod));
return ret + mod * (ret < 0) - mod * (ret >= (ll)mod);
}
 
unsigned long long mod_pow(unsigned long long x, unsigned long long k, unsigned long long mod){
     unsigned long long res = 1;
     while(k){
         if(k & 1) res = mod_mul(res, x, mod);
         x = mod_mul(x, x, mod);
         k >>= 1;
     }
     return res;
 }
 
bool check(unsigned long long n){
    if(n < 2 || ((n % 6 != 1) && (n % 6 != 5))) return (n == 2) || (n == 3);
    unsigned long long d = n - 1, s = 0;
    while(d % 2 == 0){
        d /= 2;
        s++;
    }
    for(unsigned long long a : numset){
        if(a % n == 0) return true;
        unsigned long long res = mod_pow(a, d, n);
        if(res == 1) continue;
        bool ok = true;
        for(unsigned int r = 0; r < s; r++){
            if(res == n-1){
                ok = false;
                break;
            }
                         res = mod_mul(res, res, n);
        }
        if(ok) return false;
    }
    return true;
}

const int mx = 1e6;
vector<ll> p;
int cnt[mx+1];
int main(){
    int n;
    cin>>n;
    while(n--){
        ll now;
        cin>>now;
        if(check(now)) cout<<now<<" "<<1<<endl;
        else cout<<now<<" "<<0<<endl;
    }
    return 0;
    for(int i = 2;i<=mx;i++){
        if(cnt[i]) continue;
        p.push_back(i);
        for(int j = i;j<=mx;j+=i) cnt[j] = i;
    }
    mint ans = 1;
    ll k;
    cin>>n>>k;
    for(int i = 0;i<p.size();i++){
        ll cnt = 0;
        cnt += calc(n,p[i]) - calc(n-k,p[i]) - calc(k,p[i]);
        assert(cnt>=0);
        if(cnt) ans *= mint(cnt+1);
    }
    for(ll i = n;i>n-k;i--) if(i>=mx){
        if(check(i)) {
            ans *= calc(n,i) + 1;
        }
    }
    cout<<ans<<endl;

}
0