結果

問題 No.1661 Sum is Prime (Hard Version)
コンテスト
ユーザー LayCurse
提出日時 2021-07-29 21:28:04
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,156 ms / 3,000 ms
コード長 2,041 bytes
コンパイル時間 2,397 ms
コンパイル使用メモリ 193,700 KB
最終ジャッジ日時 2025-01-23 10:13:22
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:50:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |   scanf("%lld%lld",&L,&R);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

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