-
Notifications
You must be signed in to change notification settings - Fork 0
/
UVa 10856.cpp
132 lines (120 loc) · 3.76 KB
/
UVa 10856.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/*BISMILLAHIR RAHMANIR RAHIM*/
#include<bits/stdc++.h>
#define lli long long int
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define ALL(x) x.begin(), x.end()
#define PI acos(-1.0)
#define nl cout<<"\n"
#define print(x) cout<<x<<endl;
#define mem(ar, val) memset(ar, val, sizeof(ar))
#define point(x) fixed<<setprecision(x)
#define printcase(n) cout << "Case " << tc << ": " << n <<endl;
#define printcaseii(n, m) cout << "Case " << tc << ": " << n << " " << m <<endl;
#define aInput(ar, n) for(int i=0; i<n; i++)cin>>ar[i];
#define vInput(v, n) for(int i=0; i<n; i++){lli xwq;cin>>xwq;v.push_back(xwq);}
#define input2D(ar, row, col) for(int i=0; i<row; i++){for(int j=0; j<col; j++){cin >> ar[i][j];}}
#define print2D(ar, row, col) for(int i=0; i<row; i++){for(int j=0; j<col; j++){cout << ar[i][j] << " ";}cout<<endl;}
#define vprint(vec) for(int i=0; i<vec.size(); i++){cout << vec[i]; (i==vec.size()-1? cout<<endl : cout<<" ");}
#define aprint(ar, n) for(int i=0; i<n; i++){cout << ar[i] << " ";}cout<<endl
#define ANUPAM_AKIB ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define execution_time cerr<<endl;int z=30;while(z--){cerr<<'-';}cerr<<endl;cerr<<point(16)<<"**Time -> "<<(double)(clock()-tStart)/CLOCKS_PER_SEC<<"fs"<<endl;
#define INPUT freopen("input.txt", "r", stdin)
#define OUTPUT freopen("output.txt", "w", stdout)
#define umap unordered_map
#define _IN input()
#define IN input()
#define yo(x) cout<<(#x)<<" = "<<(x)<<endl;
#define loop(n) for(int ctrx=0; ctrx<n; ctrx++)
#define ff first
#define ss second
#define VEC vector<lli>
#define sz size()
using namespace std;
const lli inf = 1e9;
const int mod = 1e6+7;
lli findLCM(lli a, lli b){return ((a*b)/__gcd(a,b));}
lli input(){lli x; cin >> x; return x;}
int digitCNT(int n){return ceil(log10(n)+0.00000001);}
string to_binary(lli num){if(num==0) return ""; return to_binary(num/2)+to_string(num%2);}
lli to_decimal(string s){lli r = 0, p = 1;for(int i=s.sz-1; i>=0; i--){if(s[i] == '1') r += p; p *= 2;}return r;}
bool isPalindrome(string s){for(int i=0, j=s.size()-1; i<s.size()/2; i++, j--){if(s[i]!=s[j]) return 0;}return 1;}
bool isPrime(lli n){if(n<2){return false;}if(n==2||n==3){return true;}if(n%2==0){return false;}for(lli i=3; i*i<=n; i+=2){if(n%i==0){return false;}}return true;}
bool cmp(int a, int b){
return a>b;
}
const int maxN = 2703663;
int NUM = maxN;
bool mark[maxN];
vector<int> prime;
void sieve(){
//true = not prime
//false = prime
for(int i=4; i<=NUM; i+=2){
mark[i]=true;
}
for(int i=3; i*i<=NUM; i+=2){
if(mark[i]==false){
for(int j=i*i; j<=NUM; j+=(i+i)){
mark[j]=true;
}
}
}
for(int i=2; i<=NUM; i++){
if(mark[i]==false){
prime.push_back(i);
}
}
}
int cnt[maxN+2];
int res[10000002];
void precal(){
sieve();
for(int i=2; i<=maxN; i++){
int k = i, j=0, c=1;
while(mark[k]){
if(k%prime[j]==0){
k /= prime[j];
c++;
}
else{
j++;
}
}
cnt[i] = cnt[i-1] + c;
}
mem(res, -1);
for(int i=0; i<=maxN; i++){
res[cnt[i]] = i;
}
}
int tt = 1;
void solve(lli tc){
int n = tc;
res[0] = 0;
if(res[n]!=-1){
print("Case " << tt++ << ": " << res[n] << "!");
}
else{
print("Case " << tt++ << ": Not possible.");
}
}
int main(){
ANUPAM_AKIB;
#ifndef ONLINE_JUDGE
clock_t tStart = clock();
INPUT;
OUTPUT;
#endif
precal();
lli tc = 1;
/*cin >> tc; //TEST CASE
for(int i=1; i<=tc; i++){
solve(i);
}*/
while(cin >> tc && tc>=0) solve(tc); //EOF
#ifndef ONLINE_JUDGE
execution_time;
#endif
return EXIT_SUCCESS;
}