結果

問題 No.308 素数は通れません
ユーザー moti
提出日時 2015-12-02 08:02:32
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,860 bytes
コンパイル時間 1,455 ms
コンパイル使用メモリ 121,820 KB
実行使用メモリ 13,760 KB
最終ジャッジ日時 2024-09-14 07:51:04
合計ジャッジ時間 5,139 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 62 WA * 1 TLE * 1 -- * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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}, 
};

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;
  }
  */
  if(N % 8 == 1 && miller_rabin_primality_test(N-8, 100)) {
    cout << 14 << endl;
  }
  else {
    cout << 8 << endl;
  }


  return 0;
}
0