結果

問題 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,812 ms / 3,000 ms
コード長 1,705 bytes
コンパイル時間 2,267 ms
コンパイル使用メモリ 203,104 KB
実行使用メモリ 7,660 KB
最終ジャッジ日時 2024-11-21 00:10:20
合計ジャッジ時間 17,100 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 10 ms
7,500 KB
testcase_01 AC 9 ms
7,488 KB
testcase_02 AC 1,222 ms
7,616 KB
testcase_03 AC 10 ms
7,476 KB
testcase_04 AC 9 ms
7,544 KB
testcase_05 AC 10 ms
7,484 KB
testcase_06 AC 9 ms
7,380 KB
testcase_07 AC 10 ms
7,532 KB
testcase_08 AC 10 ms
7,368 KB
testcase_09 AC 10 ms
7,504 KB
testcase_10 AC 10 ms
7,524 KB
testcase_11 AC 9 ms
7,448 KB
testcase_12 AC 1,311 ms
7,464 KB
testcase_13 AC 1,016 ms
7,540 KB
testcase_14 AC 515 ms
7,484 KB
testcase_15 AC 1,100 ms
7,452 KB
testcase_16 AC 1,664 ms
7,536 KB
testcase_17 AC 1,207 ms
7,616 KB
testcase_18 AC 58 ms
7,660 KB
testcase_19 AC 744 ms
7,596 KB
testcase_20 AC 1,125 ms
7,400 KB
testcase_21 AC 618 ms
7,544 KB
testcase_22 AC 1,226 ms
7,536 KB
testcase_23 AC 1,812 ms
7,432 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