fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef  long long ll;
  6. typedef long double ld;
  7.  
  8. #define pb push_back
  9.  
  10. const int N=1e6+50,mod=10000007;
  11. int prim[N],vis[N],it,dp[N];
  12. int ansVis[N];
  13. int ansdp[N];
  14. unordered_map<int,int> mp(N);
  15. vector<int> vect;
  16.  
  17. void sieve(){
  18.     for (int i=2;i*i<N;i++){
  19.         if (!prim[i]){
  20.             for (int j=i+i;j<N;j+=i)
  21.                 prim[j]=i;
  22.         }
  23.     }
  24.     for (int i=2;i<N;i++){
  25.         if (!prim[i]){
  26.             prim[i]=i;
  27.             vect.pb(i);
  28.         }
  29.     }
  30.     return;
  31. }
  32.  
  33. ll solve(int ind){
  34.     if (ind==-1)
  35.         return 1;
  36.     if (vis[ind]==it)
  37.         return dp[ind];
  38.     ll ret=0;
  39.     for (long long i=0;i<=mp[vect[ind]];i++){
  40.         ret+=solve(ind-1)*(i+1);
  41.         if(ret>mod)
  42.           ret%=mod;
  43.     }
  44.     dp[ind]=ret;
  45.     vis[ind]=it;
  46.     return ret;
  47. }
  48.  
  49. int main(){
  50.     ios_base::sync_with_stdio(0);
  51.     cin.tie(0);
  52.     sieve();
  53.     int n,x;
  54.     while(cin>>n && n){
  55.         if(ansVis[n]){
  56.             cout<<ansdp[n]<<"\n";
  57.             continue;
  58.         }
  59.         mp.clear();
  60.         for (int i=1;i<=n;i++){
  61.             x=i;
  62.             while(prim[x]){
  63.                 mp[prim[x]]++;
  64.                 x/=prim[x];
  65.             }
  66.         }
  67.         ll ans=0;
  68.         int siz=vect.size();
  69.         it++;
  70.         for (int i=30000; i<siz+29999;i+=30000){
  71.             ans=solve(min(i,siz-1));
  72.         }
  73.         ansVis[n]=1;
  74.         ansdp[n]=ans;
  75.         cout<<ans<<"\n";
  76.     }
  77.     return 0;
  78. }
Success #stdin #stdout 0.01s 15876KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qle3IC
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!