fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<ll, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. // K = p_1^a_1 * p_2 ^ a_2 * ... * p_n^a_n
  11. // Với mỗi thừa số p_i thì cần tìm N_i nhỏ nhất sao cho (N_i)! chia hết cho p_i^a_i
  12. // Đáp án chính là max của các N_i
  13. ll K;  
  14.  
  15. vector<ii> factorize(ll x) {
  16. 	vector<ii> ans;  
  17. 	for (ll i = 2; i * i <= x; i++) {
  18. 		if (x % i == 0) {
  19. 			int e = 0;   
  20. 			while (x % i == 0) x /= i, e++; 
  21. 			ans.push_back({i, e}); 
  22. 		}
  23. 	}
  24. 	if (x > 1) ans.push_back({x, 1}); 
  25.  
  26. 	return ans; 
  27. }
  28.  
  29. int main() {
  30. 	ios::sync_with_stdio(0); cin.tie(0);  	
  31. 	cin >> K;   
  32.  
  33. 	vector<ii> d = factorize(K); 
  34. 	ll ans = 0;                                          
  35. 	for (ii p : d) {
  36. 		ll N = 0; int e = 0;  
  37. 		while (e < p.second) {
  38. 			N += p.first;  
  39. 			ll tmp = N;   
  40. 			while (tmp % p.first == 0) tmp /= p.first, e++;   
  41. 		}
  42.  
  43. 		ans = max(ans, N); 
  44. 	}
  45.  
  46. 	cout << ans << '\n'; 
  47. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
123456789011
stdout
copy 
123456789011
https://ideone.com/4Rq6h3
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!