yicongli

Gym 313459E

Jan 24th, 2021
519
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define gc c=getchar()
  6. #define r(x) read(x)
  7. #define ll long long
  8.  
  9. template<typename T>
  10. inline void read(T&x){
  11.     x=0;T k=1;char gc;
  12.     while(!isdigit(c)){if(c=='-')k=-1;gc;}
  13.     while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
  14. }
  15.  
  16. const int N=1e6+7;
  17.  
  18. bool mark[N];
  19. int prime[N],tot;
  20. bool vis[N];
  21.  
  22. int main(){
  23.     // freopen(".in","r",stdin);
  24.     // freopen(".out","w",stdout);
  25.     ll s,e,k;r(s),r(e),r(k);
  26.     int n=e-s+1;
  27.     ll ans=0;
  28.     for(int i=2,cnt=0;cnt<k;++i){
  29.         if(!mark[i]){
  30.             prime[++tot]=i;
  31.             for(int x=(i-s%i)%i;cnt<k&&x<n;x+=i){
  32.                 if(!vis[x]){
  33.                     vis[x]=1;
  34.                     ans+=i;
  35.                     ++cnt;
  36.                 }
  37.             }
  38.         }
  39.         for(int j=1,tmp;j<tot&&(tmp=i*prime[j])<N;++j){
  40.             mark[tmp]=1;
  41.             if(i%prime[j]==0)break;
  42.         }
  43.     }
  44.     printf("%lld\n",ans);
  45.     return 0;
  46. }
RAW Paste Data