結果

問題 No.1661 Sum is Prime (Hard Version)
ユーザー monnumonnu
提出日時 2021-08-31 02:23:54
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,361 bytes
コンパイル時間 1,742 ms
コンパイル使用メモリ 182,092 KB
実行使用メモリ 14,008 KB
最終ジャッジ日時 2024-05-03 13:45:45
合計ジャッジ時間 32,559 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
10,660 KB
testcase_01 AC 1 ms
6,948 KB
testcase_02 AC 2,757 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 WA -
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2,371 ms
6,940 KB
testcase_13 AC 2,312 ms
6,940 KB
testcase_14 AC 2,812 ms
6,940 KB
testcase_15 TLE -
testcase_16 AC 2,908 ms
6,948 KB
testcase_17 AC 2,705 ms
6,944 KB
testcase_18 AC 1,019 ms
6,940 KB
testcase_19 AC 1,902 ms
6,940 KB
testcase_20 AC 1,081 ms
6,940 KB
testcase_21 AC 2,316 ms
6,940 KB
testcase_22 TLE -
testcase_23 -- -
権限があれば一括ダウンロードができます

ソースコード

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