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

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	nmnmnmnmnmnmnm
提出日時	2015-12-01 01:20:30
言語	C++11 (gcc 11.4.0)
結果	WA
実行時間	-
コード長	3,856 bytes
コンパイル時間	571 ms
コンパイル使用メモリ	85,972 KB
実行使用メモリ	4,356 KB
最終ジャッジ日時	2023-10-12 06:33:43
合計ジャッジ時間	3,746 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define clr(a, b) memset((a), (b) ,sizeof(a))

#define MOD 1000000007

int isPrime(int n){
  int i;

  if(n < 2){
    return 0;
  }
  else if(n == 2){
    return 1;
  }

  if(n % 2 == 0){
    return 0;
  }
 
  for(i = 3; i * i <= n; i += 2){
    if(n % i == 0){
      return 0;
    }
  }

  return 1;
}

int d[10000][30];

int main(){
  long long n;
  cin>>n;
  int d[1000] = {
    -1,-1,-1,-1,3,-1,5,-1,7,7,7,
    -1,11,-1,13,7,7,-1,8,-1,19,
    19,7,-1,23,23,8,8,8,-1,8,
    -1,8,8,8,8,8,-1,8,8,8,
    -1,8,-1,8,8,8,-1,8,14,8,
    8,8,-1,8,8,8,8,8,-1,8,
    -1,8,8,8,8,8,-1,8,8,8,
    -1,8,-1,8,8,8,8,8,-1,8,
    14,8,-1,8,8,8,8,8,-1,8,
    8,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,14,8,-1,8,-1,8,8,8,-1,8,8,8,8,8,8,8,14,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,-1,8,-1,8,8,8,8,8,14,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,-1,8,8,8,8,8,8,8,8,8,-1,8,-1,8,8,8,-1,8,-1,8,14,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,-1,8,8,8,8,8,-1,8,-1,8,8,8,8,8,8,8,14,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,14,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,8,8,14,8,8,8,-1,8,8,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,-1,8,8,8,14,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,14,8,-1,8,-1,8,8,8,-1,8,8,8,8,8,-1,8,14,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,14,8,-1,8,-1,8,8,8,8,8,8,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,14,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,14,8,-1,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,8,8,-1,8,-1,8,8,8,8,8,14,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,14,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,-1,8,8,8,8,8,-1,8,14,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,8,8,14,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,-1,8,-1,8,8,8,-1,8,14,8,8,8,-1,8,8,8,8,8,-1,8,-1,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,-1,8,8,8,14,8,-1,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,-1,8,8,8,14,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,8,8,-1,8,-1,8,8,8,8,8,14,8,8,8,-1,8,-1,8,8,8,-1,8,-1,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,-1,8,14,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,-1,8,-1,8,8,8,-1,8,14,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,8,8,-1,8,8,8,8,8,8,8,-1,8,8,8,-1,8,8,8,14,8,-1,8,8,8,8,8,-1,8,8,8,8,8,8,8,14,8,8,8,8,8,-1,8,8,8,-1,8,8,8,8,8,-1,8,8,8,8,8,-1,8,14,8,8,8,8,8,-1,8,8,8,8,8,-1,8,8};
  if(n<1000){
    cout << d[n] << endl;
    return 0;
  }
  long long a = n-1;
  long long b = n-8;
  long long c = n-7;
  long long e = n-16;
  if(a%8==0){
    rep(i,2,100000){
      if(isPrime(i)==1){
        if(b%i==0){
          cout << "8" << endl;
          return 0;
        }
      }
    }
    int flag1 = 0;
    int flag2 = 0;
    rep(i,2,100000){
      if(isPrime(i)==1){
        if(c%i==0){
          flag1 = 1;
        }
        if(e%i==0){
          flag2 = 1;
        }
      }
    }
    if(flag1 == 1 || flag2 == 1){
      cout << "8" << endl;
      return 0;
    }
    cout << "14" << endl;
    return 0;
  }
  else{
    cout << "8" << endl;
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード