結果

問題 No.1661 Sum is Prime (Hard Version)
ユーザー LayCurseLayCurse
提出日時 2021-07-29 21:23:46
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,735 ms / 3,000 ms
コード長 1,705 bytes
コンパイル時間 2,388 ms
コンパイル使用メモリ 202,368 KB
実行使用メモリ 7,704 KB
最終ジャッジ日時 2024-05-01 01:02:43
合計ジャッジ時間 16,645 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
7,600 KB
testcase_01 AC 9 ms
7,544 KB
testcase_02 AC 1,162 ms
7,524 KB
testcase_03 AC 9 ms
7,512 KB
testcase_04 AC 8 ms
7,448 KB
testcase_05 AC 9 ms
7,568 KB
testcase_06 AC 9 ms
7,676 KB
testcase_07 AC 9 ms
7,552 KB
testcase_08 AC 9 ms
7,524 KB
testcase_09 AC 9 ms
7,580 KB
testcase_10 AC 10 ms
7,568 KB
testcase_11 AC 11 ms
7,620 KB
testcase_12 AC 1,272 ms
7,604 KB
testcase_13 AC 987 ms
7,536 KB
testcase_14 AC 507 ms
7,528 KB
testcase_15 AC 1,055 ms
7,660 KB
testcase_16 AC 1,593 ms
7,620 KB
testcase_17 AC 1,161 ms
7,520 KB
testcase_18 AC 57 ms
7,704 KB
testcase_19 AC 718 ms
7,596 KB
testcase_20 AC 1,080 ms
7,536 KB
testcase_21 AC 594 ms
7,516 KB
testcase_22 AC 1,180 ms
7,608 KB
testcase_23 AC 1,735 ms
7,564 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int ps, p[1000000];
ll memo[] = {16252325,31324703,46009215,60454705,74726528,88862422,102886526,116818447,130670192,144449537,158165829,171827136,185436625,198996103,212514323,225991743,239429993,252834065,266206294,279545368,292856421,306137611,319391721,332620900,345826612,359006517,372168766,385307831,398425675,411523195,424603409,437663672,450708777,463733626,476741968,489736021,502712575,515673696,528624525,541555851,554476170,567382703,580275482,593155089,606022680,618878615,631717982,644550922,657371139,670180516,682979568,695766925,708543557,721310048,734065508,746813071,759550004,772276773,784994469,797703398,810401956,823092766,835773764,848450250,861116918,873772692};
bitset<500000> b;

ll solve(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 / 300000000;
  if(s){
    res = memo[s-1];
    s *= 300000000;
  } 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;
}

int main(){
  int i, j;
  ll L, R;
  scanf("%lld%lld",&L,&R);

  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;

  printf("%lld\n", solve(2*R) - solve(2*L) + solve(R) - solve(L-1));
}
0