fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7. typedef long long ll;
  8. const ll INF = 1LL << 50;
  9.  
  10. int solve();
  11.  
  12. ll gcd(ll p, ll q) {
  13. 	if (q == 0) { return p; }
  14. 	return gcd(q, p%q);
  15. }
  16.  
  17. int main(void) {
  18. 	while (solve()) {}
  19. 	return 0;
  20. }
  21.  
  22. int solve() {
  23.  
  24. 	ll p, q, g;
  25.  
  26. 	cin >> p >> q;
  27.  
  28. 	g = gcd(max(p, q), min(p, q));
  29.  
  30. 	//	約分
  31. 	p = p / g;
  32. 	q = q / g;
  33.  
  34. 	//	エラトステネスの篩
  35.  
  36. 	const ll M = sqrt(10e9) + 1;
  37. 	std::vector< bool > isPrime(M, true);
  38. 	isPrime[1] = false;
  39.  
  40. 	for (ll i = 2; i < M; i++) {
  41. 		if (isPrime[i] == false) { continue; }
  42. 		for (ll j = i; i * j < M; j++) {
  43. 			isPrime[i*j] = false;
  44. 		}
  45. 	}
  46.  
  47. 	ll ans = 1;
  48. 	for (ll i = 2; i < M; i++) {
  49. 		if (q % i == 0 && isPrime[i] == true ) {
  50. 			ans *= i;
  51. 		}
  52. 	}
  53.  
  54. 	if( q > 1 && ans == 1 ) { ans = q;}
  55.  
  56.  
  57. 	cout << ans << endl;
  58.  
  59.  
  60. 	return 0;
  61. }
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
1 999002449
stdout
copy 
31607
https://ideone.com/NCk3Dp
language:
C++14 (gcc 8.3)
created:
6 years 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!