fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. const int mxn = 1e7+1;
  6.  
  7.  
  8. int fact[mxn+1];
  9. vector<int> criba(mxn+1,-1);
  10.  
  11. void sieve(){
  12.  
  13.     criba[0] = criba[1] = 1;
  14.     for(int i = 2; i <= mxn; i++){
  15.         if(criba[i] == -1){
  16.             for(int j = i*i; j <= mxn; j += i)
  17.                 if(criba[j] == -1)
  18.                     criba[j] = i;
  19.         }
  20.     }
  21.     for(int i = 2; i <= mxn; i++)
  22.         if(criba[i] == -1)
  23.             criba[i] = i;
  24. }
  25.  
  26. int divs(int n){
  27.     if(n == 1)return 0;
  28.     int ans = 0, divi = criba[n];
  29.     while(n % divi == 0){
  30.         ans++;
  31.         n /= divi;
  32.     }
  33.     return ans + divs(n);
  34. }
  35.  
  36. void preFact(){
  37.     fact[0] = fact[1] = 0;
  38.     for(int i = 2; i <= mxn; i++)
  39.         fact[i] = fact[i-1] + divs(i);
  40. }
  41.  
  42. void solve(){
  43.     int n;
  44.     int it = 0;
  45.     while(cin >> n){
  46.         if(n == -1)break;
  47.  
  48.         int lo = 0, hi = mxn, ans = -1;
  49.         while(lo <= hi){
  50.             int mid = lo + (hi-lo)/2;
  51.             if(fact[mid] >= n){
  52.                 if(fact[mid] == n)ans = mid;
  53.                 hi = mid-1;
  54.             }
  55.             else if(fact[mid] < n)lo = mid+1;
  56.  
  57.         }
  58.         cout << "Case " << ++it << ": ";
  59.         if(ans>=0)cout << ans << "!" << "\n";
  60.         else cout << "Not possible." << "\n";
  61.     }
  62. }
  63.  
  64. int32_t main() {
  65.     ios::sync_with_stdio(false);
  66.     cin.tie(0);
  67. 	sieve();
  68. 	preFact();
  69. 	solve();
  70.  
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 1.55s 159300KB
comments (?)
stdin
copy 
1
2
3
-1
stdout
copy 
Case 1: 2!
Case 2: 3!
Case 3: Not possible.
https://ideone.com/KS9y9R
language:
C++ (gcc 8.3)
created:
3 days 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!