fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define faster() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  4. // Hàm này dùng để tính số mũ của số y khi phân tích x! ra thừa số nguyên tố
  5. long long gt(long long x, long long y){
  6. 	long long dem=0;
  7. 	while (x!=0){
  8. 		dem+=x/y;
  9. 		x/=y;
  10. 	}
  11. 	return dem;
  12. }
  13. // Dùng để xử lý
  14. void solve(){
  15. 	long long n, k;
  16. 	cin >> n >> k;
  17.     long long min=1e18;
  18. 	for (int i=2;i<=sqrt(k);i++){
  19. 		if (k%i==0){
  20.             // Đếm số mũ của 1 thừa số nguyên tố phân tích số n
  21. 			long long d=0;
  22. 			while (k%i==0){
  23. 				d++;
  24. 				k/=i;
  25. 			}
  26. 			long long t=(gt(n, i))/d;
  27.             // kết quả là thương của 2 số mũ khi phân tích n! và k ra thừa số nguyên tố
  28. 			if (t<min) min=t;
  29. 		}
  30. 	}
  31. 	if (k>1 && gt(n, k)<min) min=gt(n, k);
  32. 	cout << min << "\n";
  33. }
  34. int main(){
  35. 	faster();
  36. 	int t;
  37. 	cin >> t;
  38. 	while (t--) solve();
  39. }
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
2
5 3
15 5
stdout
copy 
1
3
https://ideone.com/VoD3xS
language:
C++ (gcc 8.3)
created:
2 years 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!