結果

問題 No.1661 Sum is Prime (Hard Version)
コンテスト
ユーザー monnu
提出日時 2021-08-31 02:23:54
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 4,361 bytes
コンパイル時間 2,581 ms
コンパイル使用メモリ 182,048 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-12-30 16:58:58
合計ジャッジ時間 48,623 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 13 WA * 1 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

ll counting_primes(ll x){
  if(x<=70){
    vector<int> p_table(x+1,1);
    p_table[0]=0;
    p_table[1]=0;
    for(int i=2;i*i<=x;i++){
      if(p_table[i]==0){
        continue;
      }
      for(int j=2;i*j<=x;j++){
        p_table[i*j]=0;
      }
    }
    ll ret=0;
    for(int i=1;i<=x;i++){
      if(p_table[i]){
        ret++;
      }
    }
    return ret;
  }

  //P2(x,a)を計算
  ll N=1;
  while((N+1)*(N+1)*(N+1)<=x){
    N++;
  }
  ll NN=(ll)pow(x,2.0/3.0);//誤差が怖い
  vector<int> p_table(N+1,1);
  vector<ll> P;
  p_table[0]=0;
  p_table[1]=0;
  for(ll i=2;i*i<=N;i++){
    if(p_table[i]==1){
      for(ll j=2;i*j<=N;j++){
        p_table[i*j]=0;
      }
    }
  }
  for(ll i=1;i<=N;i++){
    if(p_table[i]==1){
      P.push_back(i);
    }
  }
  int n=P.size();
  ll pi1=(ll)n;
  vector<ll> cnt(N+1);
  ll pi2=-1;
  ll x_half=1;
  while((x_half+1)*(x_half+1)<=x){
    x_half++;
  }
  ll S=0;
  for(ll j=2;(j-1)*N+1<=NN;j++){
    for(int i=1;i<=N;i++){
      p_table[i]=1;
    }
    for(int i=0;i<n;i++){
      ll index=((j-1)*N/P[i]+1)*P[i];
      while(index<=j*N&&index<=NN){
        p_table[index-(j-1)*N]=0;
        index+=P[i];
      }
    }
    cnt[0]=pi1;
    for(ll i=1;i<=N&&(j-1)*N+i<=NN;i++){
      cnt[i]=cnt[i-1]+(ll)p_table[i];
      if((j-1)*N+i==x_half){
        pi2=cnt[i];
      }
    }
    ll left=max<ll>(x/(min<ll>(j*N+1,NN+1)),N);
    ll right=min<ll>(x/((j-1)*N+1),x_half);
    if(left<right){
      vector<ll> I(right-left+1,1);
      I[0]=0;
      for(int i=0;i<n&&P[i]*P[i]*P[i]*P[i]<=x;i++){
        ll index=(left/P[i]+1)*P[i];
        while(index<=right){
          I[index-left]=0;
          index+=P[i];
        }
      }
      for(ll i=left+1;i<=right;i++){
        if(I[i-left]==1){
          S+=cnt[x/i-(j-1)*N];
        }
      }
    }
    pi1=cnt[min<ll>(NN,j*N)-(j-1)*N];
  }
  S+=(ll)n*((ll)n-1)/2;
  S-=pi2*(pi2-1)/2;

  //phi(x,a)の計算
  //S1
  ll S1=0;
  vector<ll> mu(N+1,1);
  mu[0]=0;
  for(int i=0;i<n;i++){
    for(ll j=P[i];j<=N;j+=P[i]){
      mu[j]*=-1;
    }
  }
  for(int i=0;i<n&&P[i]*P[i]<=N;i++){
    for(ll j=P[i]*P[i];j<=N;j+=P[i]*P[i]){
      mu[j]=0;
    }
  }
  for(ll i=1;i<=N;i++){
    S1+=mu[i]*(x/i);
  }

  //S2
  ll S2=0;
  vector<ll> f(N+1,0);
  f[1]=x;
  for(int i=0;i<n;i++){
    for(ll j=P[i];j<=N;j+=P[i]){
      if(f[j]==0){
        f[j]=P[i];
      }
    }
  }
  ll tmp_N=N;
  int m=0;
  for(int i=0;tmp_N>0;i++,tmp_N>>=1){
    m++;
  }

  vector<ll> phi(n+1,0);
  for(ll k=1;(k-1)*N+1<=NN;k++){
    vector<vector<ll>> a(m+1,vector<ll>(N+2,0));
    for(int i=0;i<=m;i++){
      for(ll j=1;j<=(N/(1LL<<i))+1;j++){
        a[i][j]=min<ll>(1LL<<i,min<ll>(k*N,NN)-(k-1)*N-(j-1)*(1LL<<i));
      }
    }
    for(int b=0;b<n;b++){
      ll left=max<ll>(0,x/((min<ll>(k*N,NN)+1)*P[b]));
      ll right=min<ll>(N,x/(((k-1)*N+1)*P[b]));
      for(ll i=left+1;i<=right;i++){
        if(f[i]>P[b]&&mu[i]!=0){
          ll y=x/(i*P[b]);
          ll l=y-(k-1)*N;
          vector<int> e;
          for(int i=0;l>0;i++,l>>=1){
            if((l&1)==1){
              e.push_back(i);
            }
          }
          reverse(e.begin(),e.end());
          ll sum=phi[b];
          for(int r=0;r<e.size();r++){
            ll j=1;
            for(int s=0;s<r;s++){
              j+=(1LL<<(e[s]-e[r]));
            }
            sum+=a[e[r]][j];
          }
          //cout<<mu[i]<<' '<<sum<<'\n';
          S2-=mu[i]*sum;
        }
      }
      ll l=N;
      vector<int> e;
      for(int i=0;l>0;i++,l>>=1){
        if((l&1)==1){
          e.push_back(i);
        }
      }
      reverse(e.begin(),e.end());
      for(int r=0;r<e.size();r++){
        ll j=1;
        for(int s=0;s<r;s++){
          j+=(1LL<<(e[s]-e[r]));
        }
        phi[b]+=a[e[r]][j];
      }
      ll index=((k-1)*N/P[b]+1)*P[b];
      while(index<=k*N&&index<=NN){
        if(a[0][index-(k-1)*N]==1){
          ll l=index-(k-1)*N;
          for(int i=0;i<=m;i++){
            a[i][(l+(1LL<<i)-1)/(1LL<<i)]--;
          }
        }
        index+=P[b];
      }
    }
  }
  ll ret=(ll)n-S+S1+S2-1;
  //cout<<n<<" "<<S<<" "<<S1<<" "<<S2<<'\n';
  return ret;
}

int main(){
  ll L,R;
  cin>>L>>R;
  //cout<<counting_primes(x)<<'\n';
  cout<<counting_primes(R)-counting_primes(L-1)+counting_primes(2*R)-counting_primes(2*L)<<'\n';

}
0