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

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	moti
提出日時	2015-12-02 08:03:04
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	2,858 bytes
コンパイル時間	1,027 ms
コンパイル使用メモリ	118,404 KB
実行使用メモリ	8,700 KB
最終ジャッジ日時	2023-10-12 08:52:49
合計ジャッジ時間	5,240 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 8,700 KB
testcase_01	AC	2 ms 4,348 KB
testcase_02	AC	2 ms 4,352 KB
testcase_03	AC	1 ms 4,348 KB
testcase_04	AC	2 ms 4,352 KB
testcase_05	AC	2 ms 4,352 KB
testcase_06	AC	1 ms 4,352 KB
testcase_07	AC	2 ms 4,348 KB
testcase_08	AC	2 ms 4,348 KB
testcase_09	AC	2 ms 4,352 KB
testcase_10	AC	1 ms 4,348 KB
testcase_11	AC	1 ms 4,352 KB
testcase_12	AC	2 ms 4,352 KB
testcase_13	AC	2 ms 4,352 KB
testcase_14	WA	-
testcase_15	AC	1 ms 4,348 KB
testcase_16	AC	1 ms 4,352 KB
testcase_17	AC	2 ms 4,348 KB
testcase_18	AC	2 ms 4,348 KB
testcase_19	AC	1 ms 4,348 KB
testcase_20	AC	2 ms 4,348 KB
testcase_21	AC	2 ms 4,352 KB
testcase_22	AC	1 ms 4,348 KB
testcase_23	AC	2 ms 4,348 KB
testcase_24	AC	1 ms 4,348 KB
testcase_25	AC	1 ms 4,352 KB
testcase_26	AC	2 ms 4,352 KB
testcase_27	AC	2 ms 4,352 KB
testcase_28	AC	1 ms 4,352 KB
testcase_29	AC	2 ms 4,348 KB
testcase_30	AC	1 ms 4,348 KB
testcase_31	AC	1 ms 4,348 KB
testcase_32	AC	1 ms 4,352 KB
testcase_33	AC	1 ms 4,348 KB
testcase_34	AC	2 ms 4,352 KB
testcase_35	AC	2 ms 4,348 KB
testcase_36	AC	1 ms 4,348 KB
testcase_37	AC	1 ms 4,352 KB
testcase_38	AC	1 ms 4,348 KB
testcase_39	AC	1 ms 4,348 KB
testcase_40	AC	2 ms 4,352 KB
testcase_41	AC	1 ms 4,348 KB
testcase_42	AC	1 ms 4,352 KB
testcase_43	AC	2 ms 4,348 KB
testcase_44	AC	2 ms 4,348 KB
testcase_45	AC	1 ms 4,348 KB
testcase_46	AC	2 ms 4,348 KB
testcase_47	AC	2 ms 4,348 KB
testcase_48	AC	1 ms 4,352 KB
testcase_49	AC	1 ms 4,352 KB
testcase_50	AC	2 ms 4,348 KB
testcase_51	AC	1 ms 4,348 KB
testcase_52	AC	1 ms 4,348 KB
testcase_53	AC	1 ms 4,352 KB
testcase_54	AC	1 ms 4,348 KB
testcase_55	AC	1 ms 4,352 KB
testcase_56	AC	2 ms 4,348 KB
testcase_57	AC	2 ms 4,348 KB
testcase_58	AC	2 ms 4,348 KB
testcase_59	AC	2 ms 4,352 KB
testcase_60	AC	2 ms 4,348 KB
testcase_61	AC	1 ms 4,352 KB
testcase_62	AC	2 ms 4,348 KB
testcase_63	TLE	-
testcase_64	--	-
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}, 
};

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, 5)) {
    cout << 14 << endl;
  }
  else {
    cout << 8 << endl;
  }


  return 0;
}

yukicoder

結果

テストケース

ソースコード