結果

問題 No.1661 Sum is Prime (Hard Version)
コンテスト
ユーザー LayCurse
提出日時 2021-07-29 21:23:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,565 ms / 3,000 ms
コード長 1,705 bytes
コンパイル時間 1,878 ms
コンパイル使用メモリ 193,980 KB
最終ジャッジ日時 2025-01-23 10:12:45
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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[] = {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