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

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	LayCurse
提出日時	2015-12-01 00:32:46
言語	C++11 (gcc 11.4.0)
結果	RE (最新) AC (最初)
実行時間	-
コード長	27,052 bytes
コンパイル時間	3,387 ms
コンパイル使用メモリ	188,620 KB
実行使用メモリ	8,760 KB
最終ジャッジ日時	2023-08-18 12:54:03
合計ジャッジ時間	7,717 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

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

テストケース

テストケース表示

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

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

コンパイルメッセージ

main.cpp: In member function ‘int bigInt::Rshift(int, unsigned int*, int, unsigned int*)’:
main.cpp:172:3: warning: no return statement in function returning non-void [-Wreturn-type]
   }
   ^
main.cpp: In member function ‘bigInt& bigInt::operator*=(unsigned int)’:
main.cpp:912:13: warning: control reaches end of non-void function [-Wreturn-type]
     mulArray(a);
     ~~~~~~~~^~~
main.cpp: In member function ‘bigInt& bigInt::operator+=(unsigned int)’:
main.cpp:853:3: warning: control reaches end of non-void function [-Wreturn-type]
   }
   ^
main.cpp: In member function ‘bigInt& bigInt::operator/=(unsigned int)’:
main.cpp:936:13: warning: control reaches end of non-void function [-Wreturn-type]
     divArray(a);
     ~~~~~~~~^~~
main.cpp: In member function ‘bigInt& bigInt::operator-=(int)’:
main.cpp:871:3: warning: control reaches end of non-void function [-Wreturn-type]
   }
   ^
main.cpp: In member function ‘bigInt& bigInt::operator/=(int)’:
main.cpp:927:13: warning: control reaches end of non-void function [-Wreturn-type]
     divArray(val);
     ~~~~~~~~^~~~~
main.cpp: In function ‘int unsignedMillerRabinSuspect(int, unsigned int)’:
main.cpp:1139:34: warning: ‘next’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   unsigned i,t=0,u=n-1; ull now, next;
                                  ^~~~

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long
#define ull unsigned ll

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(double *x){scanf("%lf",x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}c[s]='\0';return s;}
template <class T, class S> void reader(T *x, S *y){reader(x);reader(y);}
template <class T, class S, class U> void reader(T *x, S *y, U *z){reader(x);reader(y);reader(z);}
template <class T, class S, class U, class V> void reader(T *x, S *y, U *z, V *w){reader(x);reader(y);reader(z);reader(w);}

void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(double x, char c){printf("%.15f",x);mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
void writer(const char x[], char c){int i;for(i=0;x[i]!='\0';i++)mypc(x[i]);mypc(c);}
template<class T> void writerLn(T x){writer(x,'\n');}
template<class T, class S> void writerLn(T x, S y){writer(x,' ');writer(y,'\n');}
template<class T, class S, class U> void writerLn(T x, S y, U z){writer(x,' ');writer(y,' ');writer(z,'\n');}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

char memarr[17000000]; void *mem = memarr;
#define MD 1000000007


struct bigInt{
  int sz, mem, sign;
  unsigned *d;

  static void *workMemory;
  static bigInt *writerbase;

  inline void init(void){
    mem = 0; d = NULL;
    set();
  }

  inline void init(int x){
    mem = 0; d = NULL;
    set(x);
  }

  inline void init(unsigned x){
    mem = 0; d = NULL;
    set(x);
  }

  inline void init(bigInt &x){
    mem = 0; d = NULL;
    set(x);
  }

  inline void set(void){
    sz = sign = 0;
  }

  inline void set(int x){
    if(x==0){
      set();
      return;
    }
    
    sz = 1;
    extend(sz);
    if(x < 0){
      sign *= -1;
      d[0] = -((ll)x);
    } else {
      sign = 1;
      d[0] = x;
    }
  }

  inline void set(unsigned x){
    if(x==0){
      set();
      return;
    }
    
    sz = 1;
    extend(sz);
    sign = 1;
    d[0] = x;
  }

  inline void set(bigInt &a){
    int i;
    sz = a.sz;
    sign = a.sign;
    extend(sz);
    rep(i,sz) d[i] = a[i];
  }

  inline unsigned& operator[](int n){
    return d[n];
  }

  inline void extend(int k){
    if(mem < k){
      k = max(k+1, mem+mem/2);
      d = (unsigned*) realloc(d, k*sizeof(unsigned));
      mem = k;
    }
  }

  inline void *malloc(int k, void *work){
    d = (unsigned*)work;
    mem = 2100000000;
    return d+k;
  }

  bool operator==(bigInt &a){
    int i;
    if(sign != a.sign || sz != a.sz) return false;
    rep(i,sz) if(d[i] != a.d[i]) return false;
    return true;
  }

  bool operator<(bigInt &a){
    if(sign < a.sign) return true;
    if(sign > a.sign) return false;
    if(sign==0) return false;

    if(sign * cmp(sz, d, a.sz, a.d) == -1) return true;
    return false;
  }

  inline int cmp(int as, unsigned a[], int bs, unsigned b[]){
    if(as > bs) return 1;
    if(as < bs) return -1;

    int i;
    for(i=as-1;i>=0;i--){
      if(a[i] > b[i]) return 1;
      if(a[i] < b[i]) return -1;
    }
    return 0;
  }

  inline int Lshift(int as, unsigned a[], int val, unsigned c[]){
    int i, cs, d, r;
    d = val / 32;
    r = val % 32;

    if(r){
      cs = as+d+1;
      c[cs-1] = 0;
      for(i=as-1;i>=0;i--){
        c[i+d+1] |= a[i]>>(32-r);
        c[i+d] = a[i]<<r;
      }
      rep(i,d) c[i] = 0;
      if(c[cs-1]==0) cs--;
    } else {
      for(i=as-1;i>=0;i--) c[i+d] = a[i];
      rep(i,d) c[i] = 0;
      cs = as + d;
    }
    return cs;
  }

  inline int Rshift(int as, unsigned a[], int val, unsigned c[]){
  }

  inline int add(int as, unsigned a[], unsigned b, unsigned r[]){
    int i, rs = as;
    rep(i,rs) r[i] = a[i];
    rep(i,rs){
      if(r[i]+b < r[i]){
        r[i] += b;
        b = 1;
      } else {
        r[i] += b;
        b = 0;
      }
    }
    if(b) r[rs++] = b;
    return rs;
  }

  inline int add(int as, unsigned a[], unsigned b){
    int i;
    rep(i,as){
      if(a[i]+b < a[i]){
        a[i] += b;
        b = 1;
      } else {
        a[i] += b;
        b = 0;
      }
    }
    if(b) a[as++] = b;
    return as;
  }

  inline int sub(int as, unsigned a[], unsigned b, unsigned r[]){
    int i, rs = as;
    rep(i,rs) r[i] = a[i];
    
    rep(i,rs){
      if(r[i] < b){
        r[i] -= b;
        b = 1;
      } else {
        r[i] -= b;
        break;
      }
    }
    if(rs && r[rs-1]==0) rs--;
    return rs;
  }

  inline int sub(int as, unsigned a[], unsigned b){
    int i;
    
    rep(i,as){
      if(a[i] < b){
        a[i] -= b;
        b = 1;
      } else {
        a[i] -= b;
        break;
      }
    }
    if(a[as-1]==0) as--;
    return as;
  }

  /* r=a or r=b is allowed */
  inline int add(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){
    int i, rs;
    unsigned *carry = (unsigned*) work;

    if(as < bs){
      rs = bs + 1;
      carry[0] = 0;
      rep(i,as){
        carry[i+1] = (a[i]+b[i] < a[i])?1:0;
        r[i] = a[i] + b[i];
      }
      REP(i,as,bs){
        carry[i+1] = 0;
        r[i] = b[i];
      }
      r[rs-1] = 0;
      rep(i,rs){
        if(r[i]+carry[i] < r[i]) carry[i+1]++;
        r[i] += carry[i];
      }
    } else {
      rs = as + 1;
      carry[0] = 0;
      rep(i,bs){
        carry[i+1] = (a[i]+b[i] < a[i])?1:0;
        r[i] = a[i] + b[i];
      }
      REP(i,bs,as){
        carry[i+1] = 0;
        r[i] = a[i];
      }
      r[rs-1] = 0;
      rep(i,rs){
        if(r[i]+carry[i] < r[i]) carry[i+1]++;
        r[i] += carry[i];
      }
    }

    if(rs && r[rs-1]==0) rs--;
    return rs;
  }

  inline int add(int as, unsigned a[], int bs, unsigned b[]){
    int i;
    unsigned carry;

    if(as < bs){
      REP(i,as,bs) a[i] = 0;
      as = bs;
    }

    carry = 0;
    rep(i,bs){
      if(carry){
        carry = 0;
        if(a[i]+1 < a[i]) carry = 1;
        a[i]++;
      }
      if(a[i]+b[i] < a[i]) carry = 1;
      a[i] += b[i];
    }
    while(carry){
      carry = 0;
      if(i==as) a[as++] = 0;
      if(a[i]+1 < a[i]) carry = 1;
      a[i]++;
      i++;
    }

    return as;
  }

  /* r=a or r=b is allowed */
  inline int sub(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){
    int i, rs;
    unsigned *carry = (unsigned*) work;

    carry[0] = 0;
    rs = as;
    rep(i,bs){
      if(a[i] < b[i]) carry[i+1] = 1; else carry[i+1] = 0;
      r[i] = a[i] - b[i];
    }
    REP(i,bs,as){
      carry[i+1] = 0;
      r[i] = a[i];
    }
    rep(i,as){
      if(r[i] < carry[i]) carry[i+1]++;
      r[i] -= carry[i];
    }

    while(rs && r[rs-1]==0) --rs;
    return rs;
  }

  inline int sub(int as, unsigned a[], int bs, unsigned b[]){
    int i;
    unsigned carry = 0;

    rep(i,bs){
      if(carry){
        carry = 0;
        if(a[i]==0) carry = 1;
        a[i]--;
      }
      if(a[i] < b[i]) carry = 1;
      a[i] -= b[i];
    }
    while(carry){
      carry = 0;
      if(a[i]==0) carry = 1;
      a[i]--;
      i++;
    }
    while(as && a[as-1]==0) as--;
    return as;
  }

  inline int mul(int as, unsigned a[], unsigned b, unsigned r[]){
    int i;
    ull tmp = 0;

    rep(i,as){
      tmp += (ull)b*(ull)a[i];
      r[i] = tmp&0xFFFFFFFF;
      tmp >>= 32;
    }
    if(tmp) r[as++] = tmp;
    return as;
  }

  inline unsigned div(int as, unsigned a[], unsigned b, int &ds, unsigned d[]){
    int i;
    ull tmp = 0;

    ds = as;
    for(i=ds-1;i>=0;i--){
      tmp = (tmp<<32) + a[i];
      d[i] = tmp / b;
      tmp %= b;
    }

    if(ds && d[ds-1]==0) ds--;
    return tmp;
  }

  /* r=a is allowed, r=b is not allowed */
  inline int mulSimple(int as, unsigned a[], int bs, unsigned b[], unsigned r[], void *work){
    int i, j, st, ed;
    ull sum, carry, tmp;
    unsigned *arr = (unsigned*) work;

    if(as==0 || bs==0) return 0;
    rep(i,as) arr[i] = a[i];

    sum = 0;
    carry = 0;
    rep(i,as+bs){
      st = max(0, i-as+1);
      ed = min(bs, i+1);
      REP(j,st,ed){
        tmp = (ull) arr[i-j] * b[j];
        if(sum+tmp<sum) carry++;
        sum += tmp;
      }
      r[i] = sum&0xFFFFFFFF;
      sum = (carry<<32)+(sum>>32);
      carry = 0;
    }

    as += bs;
    if(r[as-1]==0) as--;
    return as;
  }

  /* r=a is allowed, r=b is not allowed, just because this may call mulSimple */
  inline int mulKaratsuba(int as, unsigned a[], int bs, unsigned b[], unsigned c[], void *work){
    int i, j, k, ms, d;
    unsigned *c0, *c1, *c2, *ad, *bd, carry;
    int a0s, a1s, b0s, b1s, c0s, c1s, c2s, ads, bds, ac, bc, cs;

    while(as && a[as-1]==0) as--;
    while(bs && b[bs-1]==0) bs--;
    
    if(as==0 || bs==0) return 0;
    if((ll)as*bs < 10000){
      return mulSimple(as,a,bs,b,c,work);
    }

    ms = max(as, bs);
    d = (ms+1) / 2;

    a0s = min(as, d);
    a1s = as-a0s;
    b0s = min(bs, d);
    b1s = bs-b0s;

    c0 = (unsigned*)work;
    c2 = c0 + (a0s+b0s);
    c1 = c2 + (a1s+b1s);
    ad = c1 + (a0s+b0s+2);
    bd = ad + a0s;
    work = bd + b0s;

    while(a0s && a[a0s-1]==0) a0s--;
    while(b0s && b[b0s-1]==0) b0s--;
    c0s = mulKaratsuba(a0s, a, b0s, b, c0, work);
    c2s = mulKaratsuba(a1s, a+d, b1s, b+d, c2, work);

    ac = cmp(a1s, a+d, a0s, a);
    bc = cmp(b1s, b+d, b0s, b);
    if(ac==0 || bc==0){
      c1s = 0;
      c1s = add(c1s, c1, c0s, c0);
      c1s = add(c1s, c1, c2s, c2);
    } else {
      if(ac==1) ads = sub(a1s, a+d, a0s, a, ad, work);
      else      ads = sub(a0s, a, a1s, a+d, ad, work);
      if(bc==1) bds = sub(b1s, b+d, b0s, b, bd, work);
      else      bds = sub(b0s, b, b1s, b+d, bd, work);
      c1s = mulKaratsuba(ads, ad, bds, bd, c1, work);

      if(ac+bc==0){
        c1s = add(c1s, c1, c0s, c0);
        c1s = add(c1s, c1, c2s, c2);
      } else if(ac==1 && bc==1){
        c1s = sub(c2s, c2, c1s, c1, c1, work);
        c1s = add(c1s, c1, c0s, c0);
      } else {
        c1s = sub(c0s, c0, c1s, c1, c1, work);
        c1s = add(c1s, c1, c2s, c2);
      }
    }

    cs = as + bs;
    
    rep(i,c0s) c[i] = c0[i];
    REP(i,c0s,cs) c[i] = 0;

    carry = 0;
    rep(i,c1s){
      if(carry){
        carry = 0;
        if(c[i+d] + 1 < c[i+d]) carry = 1;
        c[i+d]++;
      }
      if(c[i+d]+c1[i] < c[i+d]) carry = 1;
      c[i+d] += c1[i];
    }
    while(carry){
      carry = 0;
      if(c[i+d] + 1 < c[i+d]) carry = 1;
      c[i+d]++;
      i++;
    }
    
    carry = 0;
    rep(i,c2s){
      if(carry){
        carry = 0;
        if(c[i+d+d] + 1 < c[i+d+d]) carry = 1;
        c[i+d+d]++;
      }
      if(c[i+d+d]+c2[i] < c[i+d+d]) carry = 1;
      c[i+d+d] += c2[i];
    }
    while(carry){
      carry = 0;
      if(c[i+d+d] + 1 < c[i+d+d]) carry = 1;
      c[i+d+d]++;
      i++;
    }

    if(c[cs-1]==0) cs--;
    return cs;
  }

  inline void divKaratsuba(int as, unsigned a[], int bs, unsigned b[], int &ds, unsigned d[], int &rs, unsigned r[], void *work){
    int i, p, s, t, k, shi;
    int w1s, r1s, bws, w0s, r0s;
    unsigned cof, *w1, *r1, *bw, *w0, *r0, *aa, *bb;

    while(as && a[as-1]==0) as--;
    while(bs && b[bs-1]==0) bs--;
    assert(bs!=0);

    k = cmp(bs,b,as,a);
    if(k==1){
      ds = 0;
      rs = as;
      rep(i,rs) r[i] = a[i];
      return;
    }
    
    if(bs==1){
      r[0] = div(as, a, b[0], ds, d);
      rs = 1;
      if(!r[0]) rs=0;
      return;
    }

    shi = max(0, as+1 - bs*2) + 1;

    aa = (unsigned*)work;
    bb = aa + as+shi+1;
    work = bb + bs+shi;

    cof = (1ULL<<32) / (b[bs-1]+1);
    as = mul(as, a, cof, aa);
    bs = mul(bs, b, cof, bb);
    
    shi = max(0, as - bs*2);
    if((bs+shi)%2) shi++;
    if(shi > 0){
      for(i=as-1;i>=0;i--) aa[i+shi] = aa[i];
      rep(i,shi) aa[i] = 0;
      for(i=bs-1;i>=0;i--) bb[i+shi] = bb[i];
      rep(i,shi) bb[i] = 0;
      as += shi;
      bs += shi;
    }

    p = bs / 2;
    s = max(0,as-2*p);
    
    w1s = max(0, s-bs+p+1);
    bws = p + w1s;
    r1s = max(bs + 1, bws);

    w0s = r1s-bs+p+1;
    bws = max(bws, w0s+p);
    r0s = max(bs+1, bws);

    w1 = (unsigned*)work;
    r1 = w1 + w1s;
    bw = r1 + r1s;
    w0 = bw + bws;
    r0 = w0 + w0s;
    work = r0 + r0s;

    divKaratsuba(s, aa+2*p, bs-p, bb+p, w1s, w1, r1s, r1, work);
    if(r1s){
      rep(i,r1s) r1[i+p] = r1[i];
      rep(i,p) r1[i] = 0;
      r1s += p;
    }

    s = min(p, as-p);
    r1s = add(r1s, r1, s, aa+p);
    bws = mulKaratsuba(p, bb, w1s, w1, bw, work);

    k = cmp(r1s, r1, bws, bw);
    while(k==-1){
      w1s = sub(w1s, w1, 1U);
      r1s = add(r1s, r1, bs, bb);
      k = cmp(r1s, r1, bws, bw);
    }
    if(k==1){
      r1s = sub(r1s, r1, bws, bw);
    } else {
      r1s = 0;
    }

    divKaratsuba(r1s, r1, bs-p, bb+p, w0s, w0, r0s, r0, work);
    if(r0s){
      rep(i,r0s) r0[i+p] = r0[i];
      rep(i,p) r0[i] = 0;
      r0s += p;
    }

    r0s = add(r0s, r0, p, aa);
    bws = mulKaratsuba(p, bb, w0s, w0, bw, work);

    k = cmp(r0s, r0, bws, bw);
    while(k==-1){
      w0s = sub(w0s, w0, 1U);
      r0s = add(r0s, r0, bs, bb);
      k = cmp(r0s, r0, bws, bw);
    }
    if(k==1){
      r0s = sub(r0s, r0, bws, bw);
    } else {
      r0s = 0;
    }

    ds = 0;
    if(w1s){
      ds = w1s + p;
      rep(i,w1s) d[i+p] = w1[i];
      rep(i,p) d[i] = 0;
    }
    ds = add(ds, d, w0s, w0);

    rs = max(0, r0s - shi);
    rep(i,rs) r[i] = r0[i+shi];

    div(rs, r, cof, rs, r);
  }
  
  // signを無視して c = a+b
  inline void addArray(bigInt &c, bigInt &a, bigInt &b){
    c.sz = add(a.sz, a.d, b.sz, b.d, c.d, workMemory);
  }

  // signを無視して c = a-b, 仮定 a >= b
  inline void subArray(bigInt &c, bigInt &a, bigInt &b){
    c.sz = sub(a.sz, a.d, b.sz, b.d, c.d, workMemory);
  }

  // abs(a) (>,<,=) abs(b) -> (1,-1,0)
  inline int ArrayCmp(bigInt &a, bigInt &b){
    return cmp(a.sz, a.d, b.sz, b.d);
  }

  bigInt& operator+=(bigInt &a){
    if(a.sign==0) return *this;
    if(sign==0){ set(a); return *this; }
    extend(max(sz, a.sz) + 1);

    if(sign==a.sign){
      addArray(*this, *this, a);
    } else {
      int k = ArrayCmp(*this, a);
      if(k==1){
        subArray(*this, *this, a);
      }else if(k==-1){
        subArray(*this, a, *this);
        sign *= -1;
      }else{
        a.sign = a.sz = 0;
      }
    }

    return *this;
  }

  bigInt& operator-=(bigInt &a){
    if(a.sign==0) return *this;
    if(sign==0){ set(a); sign*=-1; return *this; }
    extend(max(sz, a.sz) + 1);

    if(sign!=a.sign){
      addArray(*this, *this, a);
    } else {
      int k = ArrayCmp(*this, a);
      if(k==1){
        subArray(*this, *this, a);
      }else if(k==-1){
        subArray(*this, a, *this);
        sign *= -1;
      }else{
        a.sign = a.sz = 0;
      }
    }

    return *this;
  }

  bigInt& operator*=(bigInt &a){
    if(sign==0) return *this;
    if(a.sign==0){ set(); return *this; }
    extend(sz + a.sz);
    sign *= a.sign;

    if(this == &a){
      int i;
      unsigned *t = (unsigned*)workMemory;
      rep(i,sz) t[i] = d[i];
      sz = mulKaratsuba(sz, d, sz, t, d, t+sz);
    } else {
      sz = mulKaratsuba(sz, d, a.sz, a.d, d, workMemory);
    }

    return *this;
  }

  bigInt& operator/=(bigInt &a){
    if(sign==0) return *this;
    assert(a.sz!=0);
    sign *= a.sign;

    int dum;
    unsigned *memory = (unsigned*)workMemory;
    divKaratsuba(sz, d, a.sz, a.d, sz, d, dum, memory, memory+a.sz);

    if(sz==0) sign = 0;
    return *this;
  }

  bigInt& operator%=(bigInt &a){
    if(sign==0) return *this;
    assert(a.sz!=0);
    sign *= a.sign;

    int dum;
    unsigned *memory = (unsigned*)workMemory;
    divKaratsuba(sz, d, a.sz, a.d, dum, memory, sz, d, memory+max(0,sz-a.sz+1));

    if(sz==0) sign = 0;
    return *this;
  }

  void addArray(unsigned val){
    int i;
    rep(i,sz){
      if(d[i]+val < d[i]){
        d[i] += val;
        val = 1;
      } else {
        d[i] += val;
        val = 0;
        break;
      }
    }
    if(val){
      extend(sz+1);
      d[sz++] = val;
    }
  }

  void subArray(unsigned val){
    int i;
    
    if(sz==1){
      if(d[0] < val){
        sign = -sign;
        d[0] = val - d[0];
      } else if(d[0] > val){
        d[0] -= val;
      } else {
        sz = 0;
        sign = 0;
      }
      return;
    }
    
    rep(i,sz){
      if(d[i] < val){
        d[i] -= val;
        val = 1;
      } else {
        d[i] -= val;
        break;
      }
    }
    if(sz && d[sz-1]==0) sz--;
  }

  void mulArray(unsigned val){
    int i;
    ull tmp = 0;

    if(val==0){
      sign = sz = 0;
      return;
    }
    if(val==1){
      return;
    }

    extend(sz+1);
    rep(i,sz){
      tmp += (ull)val*(ull)d[i];
      d[i] = tmp&0xFFFFFFFF;
      tmp >>= 32;
    }
    if(tmp) d[sz++] = tmp;
  }

  unsigned divArray(unsigned val){
    int i;
    ull tmp = 0;

    assert(val != 0);
    if(val==1) return 0;

    for(i=sz-1;i>=0;i--){
      tmp = (tmp<<32) + d[i];
      d[i] = tmp / val;
      tmp %= val;
    }

    if(sz && d[sz-1]==0) sz--;
    if(sz==0) sign = 0;
    return tmp;
  }

  bigInt& operator+=(int a){
    int fg;
    unsigned val;

    if(a==0) return *this;
    if(sign==0){
      set(a);
      return *this;
    }

    if(a < 0) fg = -1, val = -((ll)a);
    else      fg = 1,  val = a;

    if(fg==sign) addArray(val);
    else         subArray(val);
  }

  bigInt& operator+=(unsigned a){
    if(a==0) return *this;
    if(sign==0){
      set(a);
      return *this;
    }

    if(sign==1) addArray(a);
    else        subArray(a);
  }

  bigInt& operator-=(int a){
    int fg;
    unsigned val;

    if(a==0) return *this;
    if(sign==0){
      set(a);
      sign *= -1;
      return *this;
    }

    if(a < 0) fg = -1, val = -((ll)a);
    else      fg = 1,  val = a;

    if(fg!=sign) addArray(val);
    else         subArray(val);
  }

  bigInt& operator-=(unsigned a){
    if(a==0) return *this;
    if(sign==0){
      set(a);
      sign *= -1;
      return *this;
    }

    if(sign!=1) addArray(a);
    else        subArray(a);
  }

  bigInt& operator*=(int a){
    int fg;
    unsigned val;

    if(a==0){
      sz = sign = 0;
      return *this;
    }
    if(sign==0){
      return *this;
    }

    if(a < 0) val = -((ll)a), sign *= -1;
    else      val = a;

    mulArray(val);
  }

  bigInt& operator*=(unsigned a){
    if(a==0){
      sz = sign = 0;
      return *this;
    }
    if(sign==0){
      return *this;
    }

    mulArray(a);
  }

  bigInt& operator/=(int a){
    int fg;
    unsigned val;

    assert(a!=0);
    if(sign==0){
      return *this;
    }

    if(a < 0) val = -((ll)a), sign *= -1;
    else      val = a;

    divArray(val);
  }

  bigInt& operator/=(unsigned a){
    assert(a!=0);
    if(sign==0){
      return *this;
    }

    divArray(a);
  }

  void add(bigInt &a, bigInt &b){
    set(a);
    (*this)+=b;
  }

  void sub(bigInt &a, bigInt &b){
    set(a);
    (*this)-=b;
  }

  void mul(bigInt &a, bigInt &b){
    set(a);
    (*this)*=b;
  }

  void div(bigInt &a, bigInt &b){
    set(a);
    (*this)/=b;
  }

  void mod(bigInt &a, bigInt &b){
    set(a);
    (*this)%=b;
  }

  void divmod(bigInt &a, bigInt &b, bigInt *d, bigInt *r){
    assert(b.sz!=0);
    d->extend(a.sz-b.sz+1);
    r->extend(b.sz);
    d->sign = r->sign = a.sign*b.sign;

    divKaratsuba(a.sz, a.d, b.sz, b.d, d->sz, d->d, r->sz, r->d, a.workMemory);

    if(d->sz==0) d->sign = 0;
    if(r->sz==0) r->sign = 0;
  }

  void reader(int as, unsigned arr[], int &rs, unsigned r[], void *work){
    int i, ss;
    unsigned *s;

    if(as < 300){
      rs = 1;
      r[0] = arr[as-1];
      for(i=as-2;i>=0;i--){
        rs = mul(rs, r, 1000000000U, r);
        rs = add(rs, r, arr[i]);
      }
      return;
    }

    for(i=0;;i++){
      if(writerbase[i].sz==0){
        writerbase[i].extend(writerbase[i-1].sz * 2);
        writerbase[i].sz = mulKaratsuba(writerbase[i-1].sz, writerbase[i-1].d, writerbase[i-1].sz, writerbase[i-1].d, writerbase[i].d, work);
        writerbase[i].sign = 1;
      }
      if((1<<i) >= as) break;
    }

    reader(as-(1<<(i-1)), arr+(1<<(i-1)), rs, r, work);
    rs = mulKaratsuba(rs, r, writerbase[i].sz, writerbase[i].d, r, work);
    s = (unsigned*)work;
    reader(1<<(i-1), arr, ss, s, s+(1<<(i-1)));
    rs = add(rs, r, ss, s);
  }

  void writer(int as, unsigned a[], int d, void *work){
    int i, k, bs, ts, ds;
    unsigned *dis, *b, *tmp;

    if(as < 100){
      dis = (unsigned*)work;
      b = dis + 9;
      tmp = b + as;

      bs = as;
      rep(i,bs) b[i] = a[i];
      
      ts = 0;
      while(bs) tmp[ts++] = div(bs, b, 1000000000U, bs, b);

      if(d==-1){
        ds = 0;
        while(tmp[ts-1]) dis[ds++] = tmp[ts-1]%10, tmp[ts-1]/=10;
        for(i=ds-1;i>=0;i--) mypc(dis[i]+'0');
        ts--;
      } else {
        i = (d - ts) * 9;
        while(i>0) i--, mypc('0');
      }
      while(ts--){
        rep(i,9) dis[i] = tmp[ts]%10, tmp[ts]/=10;
        rep(i,9) mypc(dis[8-i]+'0');
      }
    } else {
      for(i=0;;i++){
        if(writerbase[i].sz==0) writerbase[i].mul(writerbase[i-1], writerbase[i-1]);
        if(writerbase[i].sz*2 >= as) break;
      }
      b = (unsigned*)work;
      tmp = b + as - writerbase[i].sz + 1;
      work = tmp + writerbase[i].sz;
      divKaratsuba(as, a, writerbase[i].sz, writerbase[i].d, bs, b, ts, tmp, work);
      writer(bs, b, d==-1?-1:d-(1<<(i-1)), work);
      writer(ts, tmp, 1<<(i-1), work);
    }
  }

  bigInt(void){
    init();
  }

  void free(void){
    std::free(d);
  }
};

void *bigInt::workMemory;
bigInt *bigInt::writerbase;

void bigIntInit(int memsize = 20){
  int i;
  bigInt::workMemory = malloc(memsize*1000000);
  bigInt::writerbase = (bigInt*) malloc(sizeof(bigInt)*40);
  bigInt::writerbase[0].init(1U);
  bigInt::writerbase[1].init(1000000000U);
  REP(i,2,40) bigInt::writerbase[i].init();
}

void reader(bigInt *a){
  int i, j, k, sz=0, m=0;
  char *buf;
  unsigned *arr;

  for(;;){
    mygc(k);
    if(k=='-'){m=1;continue;}
    if('0'<=k&&k<='9'){break;}
  }

  buf = (char*)a->workMemory;
  buf[sz++] = k - '0';

  for(;;){
    mygc(k);
    if(k<'0' || k>'9') break;
    buf[sz++] = k - '0';
  }

  reverse(buf,buf+sz);
  arr = (unsigned*)(buf+sz);
  k = sz / 9;
  rep(i,k){
    arr[i] = 0;
    for(j=8;j>=0;j--) arr[i] = arr[i]*10 + buf[i*9+j];
  }
  if(sz%9){
    arr[k] = 0;
    for(j=sz%9-1;j>=0;j--) arr[k] = arr[k]*10 + buf[k*9+j];
    k++;
  }

  if(k < 100){
    a->set(arr[k-1]);
    for(i=k-2;i>=0;i--){
      (*a) *= 1000000000U;
      (*a) += arr[i];
    }
  } else {
    a->set(0);
    a->extend(k);
    a->sign = 1;
    a->reader(k, arr, a->sz, a->d, arr+k);
  }

  if(m) a->sign *= -1;
}

void writer(bigInt &a, char h){
  if(a.sign!=0){
    if(a.sign==-1) mypc('-');
    a.writer(a.sz, a.d, -1, a.workMemory);
  }else{
    mypc('0');
  }
  mypc(h);
}


ull unsignedMillerRabinSuspectPow(int a, unsigned k, unsigned n){
  ull p=1; unsigned bit;
  for (bit=0x80000000U;bit;bit>>=1) {
    if(p>1)   p=(p*p)%n;
    if(k&bit) p=(p*a)%n;
  }
  return p;
}

int unsignedMillerRabinSuspect(int b, unsigned n){
  unsigned i,t=0,u=n-1; ull now, next;

  while(!(u&1)) t++, u>>=1;
  now = unsignedMillerRabinSuspectPow(b, u, n);

  for(i=1;i<=t;i++){
    next=(now*now)%n;
    if(next==1 && now!=1 && now!=n-1) return 0;
    now=next;
  }
  return next==1;
}

int unsignedMillerRabin(unsigned n){
  if(n<=1)return 0; if(n<=3)return 1; if(!(n&1))return 0;
  if(!unsignedMillerRabinSuspect(2,n)) return 0;
  if(n<=1000000){
    if(!unsignedMillerRabinSuspect(3,n)) return 0;
  } else {
    if(!unsignedMillerRabinSuspect(7,n)) return 0;
    if(!unsignedMillerRabinSuspect(61,n)) return 0;
  }
  return 1;
}

bigInt ullMillerRabinSuspectPow(ull a, bigInt k, bigInt n){
  bigInt p, bit, aa;
  int i, sz;
  int arr[100];
  p.set(1U);
  bit.set(0U);

  sz = 0;
  for(;;){
    if(k==bit) break;
    arr[sz++] = k[0]&1;
    k/=2U;
  }
  while(sz--){
    p.mul(p,p);
    p.mod(p,n);
    if(arr[sz]){
      p*=(unsigned)a;
      p.mod(p,n);
    }
  }
  return p;
}

int ullMillerRabinSuspect(ull b, bigInt n){
  ull i, t = 0;
  bigInt u, now, next;
  bigInt one, n_one;

  one.set(1);
  n_one.set(n);
  n_one-=1;
  
  u.set(n_one);

  while(!(u[0]&1)) t++, u/=2;
  now = ullMillerRabinSuspectPow(b, u, n);

  for(i=1;i<=t;i++){
    next.mul(now,now);
    next.mod(next,n);
    if(next==one && !(now==one) && !(now==n_one)) return 0;
    now.set(next);
  }
  return (now==one);
}

int ullMillerRabin(bigInt n){
  int i,lim;

  if(!(n[0]&1)) return 0;
  
  lim=51;
  if(!ullMillerRabinSuspect(2,n)) return 0;
  for(i=3;i<=lim;i+=2) if(!ullMillerRabinSuspect(i,n)) return 0;

  return 1;
}

int getPrime(int N, int res[]){int i,a,b,s=1,f[4780],S=1;const int r=23000;bool B[r],*p=B;N/=2;res[0]=2;b=min(r,N);REP(i,1,b)p[i]=1;REP(i,1,b)if(p[i]){res[s++]=2*i+1;f[S]=2*i*(i+1);if(f[S]<N){for(;f[S]<r;f[S]+=res[S])p[f[S]]=0;S++;}}for(a=r;a<N;a+=r){b=min(a+r,N);p-=r;REP(i,a,b)p[i]=1;REP(i,1,S)for(;f[i]<b;f[i]+=res[i])p[f[i]]=0;REP(i,a,b)if(p[i])res[s++]=2*i+1;}return s;}

void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}

int ps, p[20000], isp[20000];
ll N, W;
int ind[20000];

char buf[20000];

int main(){
  int i, j, k;
  bigInt NN;

  bigIntInit();

  ps = getPrime(20000, p);
  rep(i,ps) isp[p[i]] = 1;

/*  REP(N,4,10000){
    if(isp[N]) continue;
    REP(W,1,N){
      unionInit(ind, N+1);
      REP(i,1,N+1){
        if(isp[i]) continue;
        if(i%W!=0 && isp[i+1]==0) unionConnect(ind, i, i+1);
        if(i+W <= N && isp[i+W]==0) unionConnect(ind, i, i+W);
      }
      if(unionGet(ind,1)==unionGet(ind,N)) break;
    }
  }*/

  reader(&NN);
  if(NN.sz>1 || NN[0]>1000){
    if(NN[0]%8!=1){ writerLn("8"); return 0; }
    NN -= 8;
    if(ullMillerRabin(NN)) writerLn("14"); else writerLn("8");
    return 0;
  } else {
    N = NN[0];
  }

    REP(W,1,N){
      unionInit(ind, N+1);
      REP(i,1,N+1){
        if(isp[i]) continue;
        if(i%W!=0 && isp[i+1]==0) unionConnect(ind, i, i+1);
        if(i+W <= N && isp[i+W]==0) unionConnect(ind, i, i+W);
      }
      if(unionGet(ind,1)==unionGet(ind,N)) break;
    }
    writerLn(W);

  return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード