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

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	moti
提出日時	2015-12-02 01:23:51
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	4,083 bytes
コンパイル時間	1,304 ms
コンパイル使用メモリ	122,776 KB
実行使用メモリ	13,756 KB
最終ジャッジ日時	2024-09-14 07:44:15
合計ジャッジ時間	5,007 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

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

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

ソースコード

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

yukicoder

結果

テストケース

ソースコード