結果

問題 No.308 素数は通れません
ユーザー keikei
提出日時 2018-10-08 23:01:52
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,746 bytes
コンパイル時間 2,140 ms
コンパイル使用メモリ 174,988 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-12 16:06:08
合計ジャッジ時間 4,280 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 ms
5,248 KB
testcase_04 RE -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 1 ms
5,248 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 1 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 1 ms
5,248 KB
testcase_22 AC 2 ms
5,248 KB
testcase_23 AC 1 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 2 ms
5,248 KB
testcase_26 AC 1 ms
5,248 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 2 ms
5,248 KB
testcase_29 AC 1 ms
5,248 KB
testcase_30 AC 1 ms
5,248 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 2 ms
5,248 KB
testcase_33 AC 1 ms
5,248 KB
testcase_34 AC 2 ms
5,248 KB
testcase_35 AC 2 ms
5,248 KB
testcase_36 AC 2 ms
5,248 KB
testcase_37 AC 2 ms
5,248 KB
testcase_38 AC 2 ms
5,248 KB
testcase_39 AC 1 ms
5,248 KB
testcase_40 AC 2 ms
5,248 KB
testcase_41 AC 2 ms
5,248 KB
testcase_42 AC 2 ms
5,248 KB
testcase_43 AC 1 ms
5,248 KB
testcase_44 AC 2 ms
5,248 KB
testcase_45 AC 2 ms
5,248 KB
testcase_46 AC 2 ms
5,248 KB
testcase_47 AC 2 ms
5,248 KB
testcase_48 AC 2 ms
5,248 KB
testcase_49 AC 1 ms
5,248 KB
testcase_50 AC 2 ms
5,248 KB
testcase_51 AC 2 ms
5,248 KB
testcase_52 AC 1 ms
5,248 KB
testcase_53 AC 1 ms
5,248 KB
testcase_54 AC 2 ms
5,248 KB
testcase_55 AC 2 ms
5,248 KB
testcase_56 AC 2 ms
5,248 KB
testcase_57 AC 1 ms
5,248 KB
testcase_58 AC 1 ms
5,248 KB
testcase_59 AC 1 ms
5,248 KB
testcase_60 AC 2 ms
5,248 KB
testcase_61 AC 2 ms
5,248 KB
testcase_62 AC 2 ms
5,248 KB
testcase_63 AC 2 ms
5,248 KB
testcase_64 AC 1 ms
5,248 KB
testcase_65 AC 2 ms
5,248 KB
testcase_66 AC 2 ms
5,248 KB
testcase_67 AC 2 ms
5,248 KB
testcase_68 AC 2 ms
5,248 KB
testcase_69 AC 2 ms
5,248 KB
testcase_70 AC 2 ms
5,248 KB
testcase_71 AC 2 ms
5,248 KB
testcase_72 AC 1 ms
5,248 KB
testcase_73 AC 2 ms
5,248 KB
testcase_74 AC 1 ms
5,248 KB
testcase_75 AC 1 ms
5,248 KB
testcase_76 AC 5 ms
5,248 KB
testcase_77 AC 2 ms
5,248 KB
testcase_78 AC 2 ms
5,248 KB
testcase_79 AC 1 ms
5,248 KB
testcase_80 AC 13 ms
5,248 KB
testcase_81 AC 16 ms
5,248 KB
testcase_82 AC 2 ms
5,248 KB
testcase_83 AC 2 ms
5,248 KB
testcase_84 AC 27 ms
5,248 KB
testcase_85 AC 2 ms
5,248 KB
testcase_86 AC 35 ms
5,248 KB
testcase_87 AC 43 ms
5,248 KB
testcase_88 AC 2 ms
5,248 KB
testcase_89 AC 2 ms
5,248 KB
testcase_90 AC 62 ms
5,248 KB
testcase_91 AC 2 ms
5,248 KB
testcase_92 AC 1 ms
5,248 KB
testcase_93 AC 2 ms
5,248 KB
testcase_94 AC 2 ms
5,248 KB
testcase_95 AC 2 ms
5,248 KB
testcase_96 AC 2 ms
5,248 KB
testcase_97 AC 2 ms
5,248 KB
testcase_98 AC 2 ms
5,248 KB
testcase_99 AC 2 ms
5,248 KB
testcase_100 AC 2 ms
5,248 KB
testcase_101 AC 79 ms
5,248 KB
testcase_102 AC 2 ms
5,248 KB
testcase_103 AC 2 ms
5,248 KB
testcase_104 AC 2 ms
5,248 KB
testcase_105 AC 2 ms
5,248 KB
testcase_106 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef __uint128_t lll;
typedef pair<int, int> pii;
typedef pair<lll, lll> pll;
const int INF = 1e9;
const lll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:https://yukicoder.me/problems/no/317>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
istream &operator>>(istream &is, __uint128_t &value) {
    string in;
    is >> in;
    value = 0;
    for (const char &c : in) {
        if ('0' <= c && c <= '9') value = 10 * value + (c - '0');
    }
    return is;
}

const ll MAX_PRIME = 10000;
vector<int> primes;
vector<int> is_prime(MAX_PRIME + 1,true);
void init_primes(){
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i <= MAX_PRIME;i++){
        if(is_prime[i]){
            primes.push_back(i);
            for(int j = i*2; j <= MAX_PRIME; j+=i) is_prime[j] = false;
        }
    }
}
// return (a * b) % m
lll mul_mod(lll a,lll b,lll m){
    lll res = 0;
    lll exp = a % m;
    while(b){
        if(b&1){
            res += exp;
            if(res > m) res -= m;
        }
        exp <<= 1;
        if(exp > m) exp -= m;
        b >>= 1;
    }
    return res;
}

// return (x ^ k) % m
lll pow_mod(lll a, lll b, lll m){
    lll res = 1;
    lll exp = a % m;
    while(b){
        if(b& 1) res = mul_mod(res, exp, m);
        exp = mul_mod(exp, exp, m);
        b >>= 1;
    }
    return res;
}

// ミラーラビン素数判定法
// return 判定値 n が 最大times回、乱択的にチェックした時に素数判定されるかどうか
bool miller_rabin(lll n, int times) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (!(n & 1)) return false;
    
    lll q = n-1;
    int k = 0;
    while (q % 2 == 0) {
        k++;
        q >>= 1;
    }
    // n - 1 = 2^k * q (qは奇素数)
    // nが素数であれば、下記のいずれかを満たす
    // (i) a^q ≡ 1 (mod n)
    // (ii) a^q, a^2q,..., a^(k-1)q のどれかがnを法として-1
    //
    // なので、逆に(i)(ii)いずれも満たしていない時は合成数と判定できる
    //
    for (int i = 0; i < times; i++) {
        lll a = rand() % (n-1) + 1; // 1,..,n-1からランダムに値を選ぶ
        lll x = pow_mod(a, q, n);
        // (i)をチェック
        if (x == 1) continue;
        // (ii)をチェック
        bool found = false;
        for (int j = 0; j < k; j++) {
            if (x == n-1) {
                found = true;
                break;
            }
            x = mul_mod(x, x, n);
        }
        if (found) continue;
        
        return false;
    }
    return true;
}

ll solve(){
    init_primes();
    ll res = 0;
    lll N; cin >> N;
    if(N <= 10){
        for(int W=3;;W++){
            vector<int> flag(N+1,0);
            flag[1] = 1;
            queue<int> q; q.push(1);
            int d[4] = {W,-W,1,-1};
            while(q.size()){
                int now = q.front(); q.pop();
                for(int k = 0; k < 4;k++){
                    if(k==2 && now%W==0)continue;
                    if(k==3 && now%W==1)continue;
                    int next = now + d[k];
                    if(next<1 && N < next) continue;
                    if(flag[next]) continue;
                    if(is_prime[next]) continue;
                    
                    flag[next] = 1;
                    q.push(next);
                }
            }
            if(flag[N]){
                res = W;
                return res;
            }
        }
    }else{
        if(N%8==1){
            if(miller_rabin(N-8, 1000)) res = 14;
            else res = 8;
        }else{
            return res = 8;
        }
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << solve() << endl;
    return 0;
}
0