#290910 (C++14) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	kei
提出日時	2018-10-08 22:51:04
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	5,315 bytes
コンパイル時間	1,991 ms
コンパイル使用メモリ	176,900 KB
実行使用メモリ	6,824 KB
最終ジャッジ日時	2024-10-12 15:59:47
合計ジャッジ時間	9,243 ms
ジャッジサーバーID （参考情報）	judge2 / judge

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	RE	-
testcase_02	RE	-
testcase_03	RE	-
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	RE	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	RE	-
testcase_12	RE	-
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	RE	-
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	RE	-
testcase_32	RE	-
testcase_33	RE	-
testcase_34	RE	-
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-
testcase_38	RE	-
testcase_39	RE	-
testcase_40	RE	-
testcase_41	RE	-
testcase_42	RE	-
testcase_43	RE	-
testcase_44	RE	-
testcase_45	RE	-
testcase_46	RE	-
testcase_47	RE	-
testcase_48	RE	-
testcase_49	RE	-
testcase_50	RE	-
testcase_51	RE	-
testcase_52	RE	-
testcase_53	RE	-
testcase_54	RE	-
testcase_55	RE	-
testcase_56	AC	2 ms 6,816 KB
testcase_57	AC	2 ms 6,816 KB
testcase_58	AC	2 ms 6,816 KB
testcase_59	AC	2 ms 6,816 KB
testcase_60	AC	2 ms 6,820 KB
testcase_61	AC	1 ms 6,820 KB
testcase_62	AC	1 ms 6,816 KB
testcase_63	AC	2 ms 6,820 KB
testcase_64	AC	2 ms 6,816 KB
testcase_65	AC	2 ms 6,816 KB
testcase_66	AC	2 ms 6,820 KB
testcase_67	AC	2 ms 6,816 KB
testcase_68	AC	2 ms 6,816 KB
testcase_69	AC	2 ms 6,820 KB
testcase_70	AC	2 ms 6,816 KB
testcase_71	AC	1 ms 6,816 KB
testcase_72	AC	2 ms 6,816 KB
testcase_73	AC	2 ms 6,820 KB
testcase_74	AC	2 ms 6,816 KB
testcase_75	AC	2 ms 6,816 KB
testcase_76	AC	6 ms 6,820 KB
testcase_77	AC	1 ms 6,816 KB
testcase_78	AC	1 ms 6,820 KB
testcase_79	AC	2 ms 6,820 KB
testcase_80	AC	13 ms 6,824 KB
testcase_81	AC	15 ms 6,820 KB
testcase_82	AC	2 ms 6,820 KB
testcase_83	AC	2 ms 6,816 KB
testcase_84	AC	25 ms 6,820 KB
testcase_85	AC	1 ms 6,820 KB
testcase_86	AC	32 ms 6,816 KB
testcase_87	AC	41 ms 6,820 KB
testcase_88	AC	2 ms 6,820 KB
testcase_89	AC	2 ms 6,820 KB
testcase_90	AC	60 ms 6,820 KB
testcase_91	AC	2 ms 6,820 KB
testcase_92	AC	2 ms 6,820 KB
testcase_93	AC	2 ms 6,816 KB
testcase_94	AC	2 ms 6,820 KB
testcase_95	AC	2 ms 6,816 KB
testcase_96	AC	2 ms 6,820 KB
testcase_97	AC	2 ms 6,816 KB
testcase_98	AC	2 ms 6,816 KB
testcase_99	AC	2 ms 6,820 KB
testcase_100	AC	2 ms 6,816 KB
testcase_101	AC	77 ms 6,820 KB
testcase_102	AC	2 ms 6,816 KB
testcase_103	AC	1 ms 6,820 KB
testcase_104	AC	2 ms 6,816 KB
testcase_105	AC	2 ms 6,820 KB
testcase_106	AC	2 ms 6,820 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include "bits/stdc++.h"
using namespace std;
//typedef long long ll;
typedef __int128_t ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll 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>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

ostream &operator<<(ostream &os, __int128_t value) {
    if (ostream::sentry(os)) {
        __uint128_t tmp = value < 0 ? -value : value;
        char buffer[64];
        char *d = end(buffer);
        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);
        if (value < 0) {
            --d;
            *d = '-';
        }
        int len = end(buffer) - d;
        if (os.rdbuf()->sputn(d, len) != len) {
            os.setstate(ios_base::badbit);
        }
    }
    return os;
}

istream &operator>>(istream &is, __int128_t &value) {
    string in;
    is >> in;
    value = 0;
    for (const char &c : in) {
        if ('0' <= c && c <= '9') value = 10 * value + (c - '0');
    }
    if (in[0] == '-') value *= -1;
    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
ll mul_mod(ll a,ll b,ll m){
    ll res = 0;
    ll 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
ll pow_mod(ll a, ll b, ll m){
    ll res = 1;
    ll 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(ll n, ll times) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (!(n & 1)) return false;
    
    ll 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++) {
        ll a = rand() % (n-1) + 1; // 1,..,n-1からランダムに値を選ぶ
        ll 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(){
    ll res = 0;
    ll N; cin >> N;
    if(N <= 10000){
        init_primes();
        for(ll W=3;W<N+10;W++){
            vector<int> flag(N+1,0);
            flag[1] = 1;
            queue<ll> q; q.push(1);
            ll 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;
                break;
            }
        }
    }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;
}