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

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	moti
提出日時	2015-12-02 01:18:40
言語	C++11 (gcc 11.4.0)
結果	RE
実行時間	-
コード長	3,911 bytes
コンパイル時間	1,514 ms
コンパイル使用メモリ	122,892 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-09-14 07:42:13
合計ジャッジ時間	16,410 ms
ジャッジサーバーID （参考情報）	judge2 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	1 ms 6,940 KB
testcase_02	AC	1 ms 6,944 KB
testcase_03	AC	1 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	1 ms 6,948 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
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	RE	-
testcase_57	RE	-
testcase_58	RE	-
testcase_59	RE	-
testcase_60	RE	-
testcase_61	RE	-
testcase_62	RE	-
testcase_63	RE	-
testcase_64	RE	-
testcase_65	RE	-
testcase_66	RE	-
testcase_67	RE	-
testcase_68	RE	-
testcase_69	RE	-
testcase_70	RE	-
testcase_71	RE	-
testcase_72	RE	-
testcase_73	RE	-
testcase_74	RE	-
testcase_75	RE	-
testcase_76	RE	-
testcase_77	RE	-
testcase_78	RE	-
testcase_79	RE	-
testcase_80	RE	-
testcase_81	RE	-
testcase_82	RE	-
testcase_83	RE	-
testcase_84	RE	-
testcase_85	RE	-
testcase_86	RE	-
testcase_87	RE	-
testcase_88	RE	-
testcase_89	RE	-
testcase_90	RE	-
testcase_91	RE	-
testcase_92	RE	-
testcase_93	RE	-
testcase_94	RE	-
testcase_95	RE	-
testcase_96	RE	-
testcase_97	RE	-
testcase_98	RE	-
testcase_99	RE	-
testcase_100	RE	-
testcase_101	RE	-
testcase_102	RE	-
testcase_103	RE	-
testcase_104	RE	-
testcase_105	RE	-
testcase_106	RE	-

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

ソースコード

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()) {
    if(vis.size() > 20) { return true; }
    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.size() > 20 || 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++; }
  assert(idx < wlist.size());
  cout << wlist[idx] << endl;

  return 0;
}

yukicoder

結果

テストケース

ソースコード