結果

問題 No.308 素数は通れません
コンテスト
ユーザー moti
提出日時 2015-12-02 01:23:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 4,083 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,304 ms
コンパイル使用メモリ 122,776 KB
実行使用メモリ 13,756 KB
最終ジャッジ日時 2024-09-14 07:44:15
合計ジャッジ時間 5,007 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 62 WA * 2 TLE * 1 -- * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <complex>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iomanip>
#include <assert.h>
#include <array>
#include <cstdio>
#include <cstring>
#include <random>
#include <functional>
#include <numeric>
#include <bitset>

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define minimize(a, x) a = std::min(a, x)
#define maximize(a, x) a = std::max(a, x)

typedef long long ll;
int const inf = 1<<29;

typedef __int128_t INT;

INT N;

bool miller_rabin_primality_test(INT p,INT iteration){

  auto modulo=[](INT a,INT b,INT c){
    INT res = 1; 
    for(INT i=0;i<b;i++){
      res *= a;
      res %= c;
    }
    return res%c;
  };

  auto mulmod = [](INT a,INT b,INT c){
    INT x = 0,y=a%c;
    while(b > 0){
      if(b%2 == 1){
        x = (x+y)%c;
      }
      y = (y*2)%c;
      b /= 2;
    }
    return x%c;
  };

  if(p<2){
    return false;
  }
  if(p!=2 && p%2==0){
    return false;
  }
  INT s=p-1;
  while(s%2==0){
    s/=2;
  }
  for(INT i=0;i<iteration;i++){
    INT a=rand()%(p-1)+1,temp=s;
    INT mod=modulo(a,temp,p);
    while(temp!=p-1 && mod!=1 && mod!=p-1){
      mod=mulmod(mod,mod,p);
      temp *= 2;
    }
    if(mod!=p-1 && temp%2==0){
      return false;
    }
  }

  return true;
}


map<INT, int> mp = {
  {4,3}, 
  {6,5}, 
  {8,7}, 
  {9,7}, 
  {10,7}, 
  {12,11}, 
  {14,13}, 
  {15,7}, 
  {16,7}, 
  {18,8}, 
  {20,19}, 
  {21,19}, 
  {22,7}, 
  {24,23}, 
};

vector<int> wlist = {8, 14, 17, 19, 20, 23, 24, 26, 27, 31, 32, 33, 34, 37, 38, 44, 45, 47, 48, 50, 53, 54, 56, 57, 59, 61, 62, 63, 64, 67, 68, 71, 73, 74, 75, 76, 77, 79, 80, 83, 84, 85, 86, 87, 89, 90, 91, 92, 93, 94, 98, 101, 103, 104, 107, 109, 110, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 128, 129, 131, 132, 133, 134, 137, 139, 140, 141, 142, 144, 145, 146, 147, 152, 153, 154, 157, 158, 159, 160, 161, 164, 168, 169, 170, 173, 174, 175, 176, 177, 182, 183, 184, 185, 186, 187, 188, 193, 194, 195, 197, 199, 200, 202, 204, 206, 207, 208, 212, 213, 214, 215, 216, 218, 220, 224, 230, 234, 236, 237, 242, 243, 244, 245, 246, 248, 254, 260, 266, 272, 274, 278, 284, 286, 290, 296, 298, 302, 304, 308, 314, 318, 320, 321, 322, 324, 326, 327, 328, 331, 332, 333, 334, 338, 340, 350, 356, 362, 364, 368, 374, 376, 380, 386, 392, 394, 398, 404, 406, 410, 412, 416, 422, 424, 434, 436, 446, 452, 464, 470, 472, 476, 482, 488, 494, 496, 499, 997, 998, 999 };

INT dx[4] = {-1,0,1,0};
INT dy[4] = {0,-1,0,1};

bool bfs(INT W, INT s) {
  queue<INT> q;
  set<INT> vis;

  q.push(s);
  vis.clear();
  vis.insert(s);

  while(!q.empty()) {

    INT p = q.front(); q.pop();
    if(s == 0 && p == N-1) { return true; }
    if(s == N-1 && p == 0) { return true; }

    INT x = p % W, y = p / W;

    rep(i, 4) {
      INT nx = x + dx[i], ny = y + dy[i];
      if(nx<0 || W<=nx || ny<0) { continue; }
      if(ny*W+nx>=N) { continue; }
      if(miller_rabin_primality_test(ny*W+nx + 1, 10)) { continue; }
      if(vis.count(ny*W+nx)) { continue; }
      vis.insert(ny*W+nx);
      q.push(ny*W+nx);
    }
  }

  return vis.count(s == 0 ? N-1 : 0);
}

int main() {

  string s; cin >> s;
  INT N = 0;
  rep(i, s.size()) {
    N *= 10;
    N += s[i] - '0';
  }

  if(mp.find(N) != mp.end()) {
    cout << mp[N] << endl;
    exit(0);
  }

  /*
  if((N-1) % 8 == 1 && miller_rabin_primality_test(N-8, 100)) {
    cout << 14 << endl;
  }
  else {
    cout << 8 << endl;
  }
  */
  int idx = 0;
  while(!bfs(wlist[idx], 0) || !bfs(wlist[idx], N-1)) { idx++; if(wlist.size() <= idx) break; }
  if(idx >= wlist.size()) {
    if((miller_rabin_primality_test(N-1, 100) || (N-1) % 8 == 1) && miller_rabin_primality_test(N-8, 100)) {
      cout << 14 << endl;
    }
    else {
      cout << 8 << endl;
    }
  }
  else {
    cout << wlist[idx] << endl;
  }

  return 0;
}
0