fork download
copy 
  1. //ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
  2. //Author: Sazid Hasan
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long              ll;
  7. typedef vector<int>            vi;
  8. #define all(a)            a.begin(),a.end()
  9. const int MAXN =          1e7+10;
  10.  
  11. vi spf(MAXN);
  12.  
  13. int bs(int mid, ll n){
  14.     int cnt = 0;
  15.     int t = n;
  16.     while(n<=mid){
  17.         cnt += mid/n;
  18.         n*=t;
  19.     }
  20.     return cnt;
  21. }
  22.  
  23. int solve(){
  24.     int m; cin >> m;
  25.     if(m==1) return 0;
  26.     int ans = 0;
  27.     while(m!=1){
  28.         if(spf[m]==m) return max(m, ans);
  29.         int cnt = 0;
  30.         int k = spf[m];
  31.         while(m%k==0){
  32.             m/=k, cnt++;
  33.         }
  34.         int st = 1, end = cnt*k;
  35.         int mid;
  36.         while(st<=end){
  37.             mid = (st+end)/2;
  38.             if(bs(mid, k)>=cnt) end = mid-1;
  39.             else st = mid+1;
  40.         }
  41.         ans = max(ans, st);
  42.     }
  43.     return ans;
  44.  
  45.     return 1;
  46. }
  47.  
  48. int main(){
  49.     ios::sync_with_stdio(false); cin.tie(nullptr);
  50.     int testcase = 1;
  51.     cin >> testcase;
  52.     iota(all(spf), 0);
  53.     for(int i = 2; i*i < MAXN; i++){
  54.         if(spf[i]==i){
  55.             for(int j = i*i; j < MAXN; j+=i){
  56.                 spf[j] = min(spf[j], i);
  57.             }
  58.         }
  59.     }
  60.     for(int tc = 1; tc <= testcase; tc++){
  61.         cout << solve() << endl;
  62.         //cout << (solve() ? "YES" : "NO") << '\n';
  63.         cerr << endl;
  64.     }
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout #stderr 0.15s 42112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
881
stderr
copy 

    

	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/0BXQd7
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
7 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!