結果

問題 No.1661 Sum is Prime (Hard Version)
ユーザー LayCurseLayCurse
提出日時 2021-07-29 21:28:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,196 ms / 3,000 ms
コード長 2,041 bytes
コンパイル時間 1,990 ms
コンパイル使用メモリ 203,204 KB
実行使用メモリ 7,660 KB
最終ジャッジ日時 2024-11-21 00:11:04
合計ジャッジ時間 12,201 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
7,496 KB
testcase_01 AC 10 ms
7,596 KB
testcase_02 AC 851 ms
7,572 KB
testcase_03 AC 10 ms
7,484 KB
testcase_04 AC 10 ms
7,464 KB
testcase_05 AC 10 ms
7,660 KB
testcase_06 AC 9 ms
7,584 KB
testcase_07 AC 9 ms
7,624 KB
testcase_08 AC 10 ms
7,560 KB
testcase_09 AC 10 ms
7,568 KB
testcase_10 AC 9 ms
7,616 KB
testcase_11 AC 9 ms
7,616 KB
testcase_12 AC 1,127 ms
7,624 KB
testcase_13 AC 618 ms
7,504 KB
testcase_14 AC 694 ms
7,600 KB
testcase_15 AC 709 ms
7,552 KB
testcase_16 AC 892 ms
7,644 KB
testcase_17 AC 802 ms
7,580 KB
testcase_18 AC 234 ms
7,568 KB
testcase_19 AC 913 ms
7,576 KB
testcase_20 AC 899 ms
7,556 KB
testcase_21 AC 13 ms
7,508 KB
testcase_22 AC 400 ms
7,628 KB
testcase_23 AC 1,196 ms
7,584 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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 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 / 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;
}

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