#685290 (C++17) No.1661 Sum is Prime (Hard Version)

提出ソース
結果

問題	No.1661 Sum is Prime (Hard Version)
ユーザー	LayCurse
提出日時	2021-08-01 20:08:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,419 ms / 3,000 ms
コード長	17,053 bytes
コンパイル時間	3,336 ms
コンパイル使用メモリ	231,964 KB
実行使用メモリ	165,668 KB
最終ジャッジ日時	2024-11-21 00:11:20
合計ジャッジ時間	15,965 ms
ジャッジサーバーID （参考情報）	judge5 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	43 ms 161,488 KB
testcase_01	AC	42 ms 161,476 KB
testcase_02	AC	877 ms 165,668 KB
testcase_03	AC	43 ms 161,592 KB
testcase_04	AC	42 ms 161,380 KB
testcase_05	AC	44 ms 161,480 KB
testcase_06	AC	43 ms 163,620 KB
testcase_07	AC	42 ms 161,532 KB
testcase_08	AC	44 ms 161,500 KB
testcase_09	AC	44 ms 161,480 KB
testcase_10	AC	43 ms 161,556 KB
testcase_11	AC	44 ms 163,620 KB
testcase_12	AC	773 ms 163,752 KB
testcase_13	AC	756 ms 163,496 KB
testcase_14	AC	856 ms 163,624 KB
testcase_15	AC	1,124 ms 163,620 KB
testcase_16	AC	922 ms 163,628 KB
testcase_17	AC	849 ms 163,624 KB
testcase_18	AC	357 ms 163,620 KB
testcase_19	AC	623 ms 163,628 KB
testcase_20	AC	382 ms 163,624 KB
testcase_21	AC	732 ms 165,548 KB
testcase_22	AC	1,419 ms 165,544 KB
testcase_23	AC	1,366 ms 163,624 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template<class T> struct cLtraits_identity{
  using type = T;
}
;
template<class T> using cLtraits_try_make_signed =
  typename conditional<
    is_integral<T>::value,
    make_signed<T>,
    cLtraits_identity<T>
    >::type;
template <class S, class T> struct cLtraits_common_type{
  using tS = typename cLtraits_try_make_signed<S>::type;
  using tT = typename cLtraits_try_make_signed<T>::type;
  using type = typename common_type<tS,tT>::type;
}
;
void*wmem;
char memarr[96000000];
template<class S, class T> inline auto max_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
  return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  walloc1d(arr, x2-x1, mem);
  (*arr) -= x1;
}
#define ISPRIME_PRE_CALC_SIZE 1000000
char isPrime_prime_table[ISPRIME_PRE_CALC_SIZE];
template<class T> inline int isPrime(T n);
void isPrime32_init(void);
int isPrime32_sub(int b, unsigned n);
int isPrime32(unsigned n);
int isPrime64_sub(long long b, unsigned long long n);
int isPrime64(unsigned long long n);
struct Rand{
  unsigned x;
  unsigned y;
  unsigned z;
  unsigned w;
  Rand(void){
    x=123456789;
    y=362436069;
    z=521288629;
    w=(unsigned)time(NULL);
  }
  Rand(unsigned seed){
    x=123456789;
    y=362436069;
    z=521288629;
    w=seed;
  }
  inline unsigned get(void){
    unsigned t;
    t = (x^(x<<11));
    x=y;
    y=z;
    z=w;
    w = (w^(w>>19))^(t^(t>>8));
    return w;
  }
  inline double getUni(void){
    return get()/4294967296.0;
  }
  inline int get(int a){
    return (int)(a*getUni());
  }
  inline int get(int a, int b){
    return a+(int)((b-a+1)*getUni());
  }
  inline long long get(long long a){
    return(long long)(a*getUni());
  }
  inline long long get(long long a, long long b){
    return a+(long long)((b-a+1)*getUni());
  }
  inline double get(double a, double b){
    return a+(b-a)*getUni();
  }
  inline int getExp(int a){
    return(int)(exp(getUni()*log(a+1.0))-1.0);
  }
  inline int getExp(int a, int b){
    return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);
  }
}
;
inline void my_putchar_unlocked(const int k){
  putchar_unlocked(k);
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int 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){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    my_putchar_unlocked(c[i]);
  }
}
template<class T> inline T pow2_L(T a){
  return a*a;
}
inline long long Isqrt_f_L(const long long n){
  long long r = sqrt(n);
  r =max_L(r-2, 0);
  while((pow2_L((r+1)))<= n ){
    r++;
  }
  return r;
}
long long llReader(long long mn, long long mx, char nx){
  int i;
  int fg = 0;
  int m = 1;
  long long res = 0;
  double tmp = 0;
  for(;;){
    i = getchar();
    if(fg==0 && i=='-'){
      fg++;
      m = -1;
    }
    else if('0' <= i  &&  i <= '9'){
      fg++;
      res = 10 * res + i - '0';
      tmp = 10 * tmp + i - '0';
      assert(tmp < 1e20);
    }
    else{
      break;
    }
  }
  assert(tmp / 2 <= res);
  assert((m==1 && fg >= 1) || (m==-1 && fg >= 2));
  assert(mn <= m * res  &&  m * res <= mx);
  assert(i == nx);
  return m * res;
}
vector<long long> ppp(20000000+1);
long long solve1(long long L, long long R){
  int i;
  long long res = 0;
  for(i=0;i<20000000+1;i++){
    if(L<=i && i<=R && ppp[i]){
      res++;
    }
  }
  for(i=0;i<20000000+1;i++){
    if(2*L+1<=i && i<=2*R-1 && ppp[i]){
      res++;
    }
  }
  return res;
}
long long solve2(long long L, long long R){
  long long k;
  long long a;
  long long b;
  long long c;
  long long res = 0;
  for(a=(L);a<(R+1);a++){
    for(b=(a);b<(R+1);b++){
      c = 0;
      for(k=(a);k<(b+1);k++){
        c += k;
      }
      if(isPrime(c)){
        res++;
      }
    }
  }
  return res;
}
int ps;
int p[1000000];
long long memo[] = {11078937,21336326,31324703,41146179,50847534,60454705,69985473,79451833,88862422,98222287,107540122,116818447,126062167,135270258,144449537,153600805,162725196,171827136,180906194,189961812,198996103,208013454,217011319,225991743,234954223,243902342,252834065,261751864,270655552,279545368,288422869,297285198,306137611,314977166,323804352,332620900,341426904,350221825,359006517,367783654,376549859,385307831,394055910,402793457,411523195,420243162,428958595,437663672,446362736,455052511,463733626,472408200,481074475,489736021,498388617,507036251,515673696,524309392,532936342,541555851,550170437,558778993,567382703,575978253,584570200,593155089,601735269,610308664,618878615,627440336,635997249,644550922,653099304,661643304,670180516,678714823,687242934,695766925,704286233,712799821,721310048,729813991,738315156,746813071,755305935,763794029,772276773,780756650,789230673,797703398,806169530,814633249,823092766,831548431,840000027,848450250,856895823,865335133,873772692,882206716};
bitset<500000> b;
long long solve3sub(long long n){
  int i;
  long long s;
  long long k;
  long long res;
  if(n < 1000000){
    for(i=0;i<ps;i++){
      if(p[i] > n){
        break;
      }
    }
    return i;
  }
  s = n / 200000000;
  if(s){
    res = memo[s-1];
    s *= 200000000;
  }
  else{
    res = ps;
    s = 1000000;
  }
  for(;;s+=1000000){
    b.set();
    for(i=1;;i++){
      k = (long long) p[i] * p[i] - s;
      if(k >= 1000000){
        break;
      }
      if(k < 0){
        k += ((-k+p[i]-1) / p[i]) * p[i];
      }
      if(k % 2 == 0){
        k += p[i];
      }
      k /= 2;
      while(k < 500000){
        b.reset(k);
        k += p[i];
      }
    }
    if(n-s < 1000000){
      for(i=1;i<=n-s;i+=2){
        res += b[i/2];
      }
      break;
    }
    res += b.count();
  }
  return res;
}
long long solve3(long long L, long long R){
  return solve3sub(2*R) - solve3sub(2*L) + solve3sub(R) - solve3sub(L-1);
}
long long cntPrime(long long n, void *mem = wmem){
  int i;
  int j;
  int sn;
  char*isp;
  long long*s1;
  long long*s2;
  long long x;
  long long c = -1;
  if(n <= 1){
    return 0;
  }
  if(n == 2){
    return 1;
  }
  sn =Isqrt_f_L(n);
  walloc1d(&s1, sn+1, &mem);
  walloc1d(&s2, sn+1, &mem);
  walloc1d(&isp, sn+1, &mem);
  s1[0] = 0;
  for(i=(1);i<(sn+1);i++){
    s1[i] = i - 1;
  }
  for(i=(1);i<(sn+1);i++){
    s2[i] = n/i - 1;
  }
  for(i=(2);i<(sn+1);i++){
    isp[i] = 1;
  }
  for(i=(2);i<(sn+1);i++){
    if(isp[i]){
      for(j=2*i;j<=sn;j+=i){
        isp[j] = 0;
      }
      c++;
      for(j=(1);j<(sn+1);j++){
        if((long long)i*i*j > n){
          goto gEg5UqEA;
        }
        x = n / j / i;
        if(x <= sn){
          s2[j] -= s1[x] - c;
        }
        else{
          s2[j] -= s2[i*j] - c;
        }
      }
      for(j=(sn+1)-1;j>=((long long)i*i);j--){
        s1[j] -= s1[j/i] - c;
      }
    }
    gEg5UqEA:;
  }
  return s2[1];
}
long long solve4(long long L, long long R){
  return cntPrime(2*R) - cntPrime(2*L) + cntPrime(R) - cntPrime(L-1);
}
int main(){
  wmem = memarr;
  {
    isPrime32_init();
  }
  long long L;
  long long R;
  long long res;
  L = llReader(1, 10000000000LL, ' ');
  R = llReader(L, 10000000000LL, '\n');
  assert(getchar() == EOF);
  res = solve4(L,R);
  wt_L(res);
  wt_L('\n');
  return 0;
  int i;
  int j;
  for(i=2;i<20000000+1;i++){
    ppp[i] = 1;
  }
  for(i=2;i<20000000+1;i++){
    if(ppp[i]){
      for(j=2*i;j<20000000+1;j+=i){
        ppp[j] = 0;
      }
    }
  }
  p[2] = 1;
  for(i=3;i<1000000;i+=2){
    p[i] = 1;
  }
  for(i=3;i<1000;i+=2){
    if(p[i]){
      for(j=i*i;j<1000000;j+=i){
        p[j] = 0;
      }
    }
  }
  for(i=0;i<1000000;i++){
    if(p[i]){
      p[ps++] = i;
    }
  }
  if(1){
    int xtzQOlbs;
    long long L;
    long long R;
    long long r1;
    long long r2;
    long long r3;
    long long r4;
    Rand rnd;
    puts("");
    for(L=(1);L<(30);L++){
      for(R=(L);R<(30);R++){
        r1 = solve1(L,R);
        r2 = solve2(L,R);
        r3 = solve3(L,R);
        r4 = solve4(L,R);
        wt_L(L);
        wt_L(' ');
        wt_L(R);
        wt_L(' ');
        wt_L(":");
        wt_L(' ');
        wt_L(r1);
        wt_L(' ');
        wt_L(r2);
        wt_L(' ');
        wt_L(r3);
        wt_L(' ');
        wt_L(r4);
        wt_L('\n');
        assert(r1==r2 && r2==r3 && r3==r4);
      }
    }
    for(xtzQOlbs=(0);xtzQOlbs<(100);xtzQOlbs++){
      L = rnd.get(1LL, 10000000000LL);
      R = rnd.get(1LL, 10000000000LL);
      if(L > R){
        swap(L, R);
      }
      ;
      r3 = solve3(L,R);
      r4 = solve4(L,R);
      wt_L(L);
      wt_L(' ');
      wt_L(R);
      wt_L(' ');
      wt_L(":");
      wt_L(' ');
      wt_L(r3);
      wt_L(' ');
      wt_L(r4);
      wt_L('\n');
      assert(r3==r4);
    }
  }
  return 0;
}
template<class T> inline int isPrime(T n){
  T i;
  if(n<=1){
    return 0;
  }
  if(n <= (1ULL<<32) - 1){
    return isPrime32(n);
  }
  if(n <= (1ULL<<63) - 1 + (1ULL<<63)){
    return isPrime64(n);
  }
  if(n<=3){
    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 isPrime32_sub(int b, unsigned n){
  unsigned i;
  unsigned t = 0;
  unsigned u = n-1;
  unsigned long long nw;
  unsigned long long nx;
  while(!(u&1)){
    t++;
    u >>= 1;
  }
  nw = 1;
  nx = b % n;
  while(u){
    if(u&1){
      nw = (nw * nx) % n;
    }
    nx = (nx * nx) % n;
    u >>= 1;
  }
  for(i=(0);i<(t);i++){
    nx = (nw * nw) % n;
    if(nx == 1 && nw != 1 && nw != n-1){
      return 0;
    }
    nw = nx;
  }
  if(nw == 1){
    return 1;
  }
  return 0;
}
int isPrime32(unsigned n){
  if(n < 100000){
    return isPrime_prime_table[n];
  }
  if(n % 2 == 0){
    return 0;
  }
  if(!isPrime32_sub(2,n)){
    return 0;
  }
  if(n<=1000000){
    if(!isPrime32_sub(3,n)){
      return 0;
    }
  }
  else{
    if(!isPrime32_sub(7,n)){
      return 0;
    }
    if(!isPrime32_sub(61,n)){
      return 0;
    }
  }
  return 1;
}
int isPrime64_sub(long long b, unsigned long long n){
  unsigned long long i;
  unsigned long long t = 0;
  unsigned long long u = n-1;
  __uint128_t nw;
  __uint128_t nx;
  while(!(u&1)){
    t++;
    u >>= 1;
  }
  nw = 1;
  nx = b % n;
  while(u){
    if(u&1){
      nw = (nw * nx) % n;
    }
    nx = (nx * nx) % n;
    u >>= 1;
  }
  for(i=(0);i<(t);i++){
    nx = (nw * nw) % n;
    if(nx == 1 && nw != 1 && nw != n-1){
      return 0;
    }
    nw = nx;
  }
  if(nw == 1){
    return 1;
  }
  return 0;
}
int isPrime64(unsigned long long n){
  if(n < 100000){
    return isPrime_prime_table[n];
  }
  if(n < (1ULL<<32)){
    return isPrime32(n);
  }
  if(n % 2 == 0){
    return 0;
  }
  if(!isPrime64_sub(2,n)){
    return 0;
  }
  if(n <= 21652684502221ULL){
    if(!isPrime64_sub(1215,n)){
      return 0;
    }
    if(!isPrime64_sub(34862,n)){
      return 0;
    }
    if(!isPrime64_sub(574237825,n)){
      return 0;
    }
  }
  else{
    if(!isPrime64_sub(325,n)){
      return 0;
    }
    if(!isPrime64_sub(9375,n)){
      return 0;
    }
    if(!isPrime64_sub(28178,n)){
      return 0;
    }
    if(!isPrime64_sub(450775,n)){
      return 0;
    }
    if(!isPrime64_sub(9780504,n)){
      return 0;
    }
    if(!isPrime64_sub(1795265022,n)){
      return 0;
    }
  }
  return 1;
}
void isPrime32_init(void){
  int i;
  int j;
  int k;
  k =Isqrt_f_L(ISPRIME_PRE_CALC_SIZE);
  for(i=(2);i<(ISPRIME_PRE_CALC_SIZE);i++){
    isPrime_prime_table[i] = 1;
  }
  for(i=(2);i<(k+1);i++){
    if(isPrime_prime_table[i]){
      for(j=(i*i);j<(ISPRIME_PRE_CALC_SIZE);j+=(i)){
        isPrime_prime_table[j] = 0;
      }
    }
  }
}
// cLay version 20210717-1 [beta]

// --- original code ---
// ll llReader(ll mn, ll mx, char nx){
//   int i, fg = 0, m = 1;
//   ll res = 0; double tmp = 0;
// 
//   for(;;){
//     i = getchar();
//     if(fg==0 && i=='-'){
//       fg++;
//       m = -1;
//     } else if('0' <= i <= '9'){
//       fg++;
//       res = 10 * res + i - '0';
//       tmp = 10 * tmp + i - '0';
//       assert(tmp < 1e20);
//     } else {
//       break;
//     }
//   }
//   assert(tmp / 2 <= res);
//   assert((m==1 && fg >= 1) || (m==-1 && fg >= 2));
//   assert(mn <= m * res <= mx);
//   assert(i == nx);
//   return m * res;
// }
// 
// 
// vector<ll> ppp(2d7+1);
// ll solve1(ll L, ll R){
//   int i;
//   ll res = 0;
//   for(i=0;i<2d7+1;i++) if(L<=i<=R && ppp[i]) res++;
//   for(i=0;i<2d7+1;i++) if(2*L+1<=i<=2*R-1 && ppp[i]) res++;
//   return res;
// }
// 
// ll solve2(ll L, ll R){
//   ll k, a, b, c, res = 0;
//   rep(a,L,R+1) rep(b,a,R+1){
//     c = 0;
//     rep(k,a,b+1) c += k;
//     if(isPrime(c)) res++;
//   }
//   return res;
// }
// 
// 
// int ps, p[1000000];
// ll memo[] = {11078937,21336326,31324703,41146179,50847534,60454705,69985473,79451833,88862422,98222287,107540122,116818447,126062167,135270258,144449537,153600805,162725196,171827136,180906194,189961812,198996103,208013454,217011319,225991743,234954223,243902342,252834065,261751864,270655552,279545368,288422869,297285198,306137611,314977166,323804352,332620900,341426904,350221825,359006517,367783654,376549859,385307831,394055910,402793457,411523195,420243162,428958595,437663672,446362736,455052511,463733626,472408200,481074475,489736021,498388617,507036251,515673696,524309392,532936342,541555851,550170437,558778993,567382703,575978253,584570200,593155089,601735269,610308664,618878615,627440336,635997249,644550922,653099304,661643304,670180516,678714823,687242934,695766925,704286233,712799821,721310048,729813991,738315156,746813071,755305935,763794029,772276773,780756650,789230673,797703398,806169530,814633249,823092766,831548431,840000027,848450250,856895823,865335133,873772692,882206716};
// bitset<500000> b;
// 
// ll solve3sub(ll n){
//   int i;
//   ll s, k, res;
// 
//   if(n < 1000000){
//     for(i=0;i<ps;i++) if(p[i] > n) break;
//     return i;
//   }
// 
//   s = n / 200000000;
//   if(s){
//     res = memo[s-1];
//     s *= 200000000;
//   } else {
//     res = ps;
//     s = 1000000;
//   }
// 
//   for(;;s+=1000000){
//     b.set();
//     for(i=1;;i++){
//       k = (ll) p[i] * p[i] - s;
//       if(k >= 1000000) break;
//       if(k < 0) k += ((-k+p[i]-1) / p[i]) * p[i];
//       if(k % 2 == 0) k += p[i];
//       k /= 2;
//       while(k < 500000) b.reset(k), k += p[i];
//     }
//     if(n-s < 1000000){
//       for(i=1;i<=n-s;i+=2) res += b[i/2];
//       break;
//     }
//     res += b.count();
//   }
// 
//   return res;
// }
// 
// ll solve3(ll L, ll R){
//   return solve3sub(2*R) - solve3sub(2*L) + solve3sub(R) - solve3sub(L-1);
// }
// 
// ll cntPrime(ll n, void *mem = wmem){
//   int i, j, sn;
//   char *isp;
//   ll *s1, *s2, x, c = -1;
//   if(n <= 1) return 0;
//   if(n == 2) return 1;
// 
//   sn = Isqrt_f(n);
//   walloc1d(&s1, sn+1, &mem);
//   walloc1d(&s2, sn+1, &mem);
//   walloc1d(&isp, sn+1, &mem);
// 
//   s1[0] = 0;
//   rep(i,1,sn+1) s1[i] = i - 1;
//   rep(i,1,sn+1) s2[i] = n/i - 1;
//   rep(i,2,sn+1) isp[i] = 1;
// 
//   rep(i,2,sn+1) if(isp[i]){
//     for(j=2*i;j<=sn;j+=i) isp[j] = 0;
//     c++;
// 
//     rep(j,1,sn+1){
//       if((ll)i*i*j > n) break_continue;
//       x = n / j / i;
//       if(x <= sn) s2[j] -= s1[x] - c;
//       else        s2[j] -= s2[i*j] - c;
//     }
//     rrep(j,(ll)i*i,sn+1){
//       s1[j] -= s1[j/i] - c;
//     }
//   }
// 
//   return s2[1];
// }
// 
// ll solve4(ll L, ll R){
//   return cntPrime(2*R) - cntPrime(2*L) + cntPrime(R) - cntPrime(L-1);
// }
// 
// {
//   ll L, R, res;
//   L = llReader(1, 1d10, ' ');
//   R = llReader(L, 1d10, '\n');
//   assert(getchar() == EOF);
// 
//   res = solve4(L,R);
//   wt(res);
//   return 0;
// 
//   int i, j;
//   for(i=2;i<2d7+1;i++) ppp[i] = 1;
//   for(i=2;i<2d7+1;i++) if(ppp[i]) for(j=2*i;j<2d7+1;j+=i) ppp[j] = 0;
// 
//   p[2] = 1;
//   for(i=3;i<1000000;i+=2) p[i] = 1;
//   for(i=3;i<1000;i+=2) if(p[i]) for(j=i*i;j<1000000;j+=i) p[j] = 0;
//   for(i=0;i<1000000;i++) if(p[i]) p[ps++] = i;
// 
//   if(1){
//     ll L, R;
//     ll r1, r2, r3, r4;
//     Rand rnd;
// 
//     puts("");
//     rep(L,1,30) rep(R,L,30){
//       r1 = solve1(L,R);
//       r2 = solve2(L,R);
//       r3 = solve3(L,R);
//       r4 = solve4(L,R);
//       wt(L,R,":",r1,r2,r3,r4);
//       assert(r1==r2==r3==r4);
//     }
// 
//     rep(100){
//       L = rnd.get(1LL, 1d10);
//       R = rnd.get(1LL, 1d10);
//       sortE(L,R);
//       r3 = solve3(L,R);
//       r4 = solve4(L,R);
//       wt(L,R,":",r3,r4);
//       assert(r3==r4);
//     }
//   }
// 
// }
yukicoder

結果

テストケース

ソースコード
