fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb(x) push_back(x)
  3. #define all(x) x.begin(), x.end()
  4. #define cout2(x, y) cout << x << " " << y <<  endl
  5. #define N 200004
  6. #define MOD 1000000007
  7.  
  8. using namespace std;
  9.  
  10. long long getSqrt(long long n){
  11.  
  12. 	long long lo = 1, hi = 1000000000, me;		
  13. 	while(lo < hi){
  14.  
  15. 		me = lo + (hi - lo + 1)/2;
  16. 		if(me * me > n)hi = me - 1;
  17. 		else lo = me;
  18. 	}
  19.  
  20. 	if(lo * lo != n)return -1;
  21. 	return lo;
  22. }
  23.  
  24. int main(){
  25.  
  26. 	int tc = 0, limit = 1000009;
  27. 	scanf("%d", &tc);
  28.  
  29. 	while(tc--){
  30.  
  31. 		long long n, phi;
  32. 		scanf("%lld%lld", &n, &phi);
  33.  
  34. 		vector<long long>ans;
  35. 		for(long long i = 2; i <= limit; i++){
  36.  
  37. 			if(n%i == 0){
  38.  
  39. 				long long p = 1;
  40. 				while(n%i == 0)p *= i, n /= i, ans.pb(i);
  41. 				phi = phi/(p - p/i);
  42. 			}
  43. 		}
  44.  
  45. 		if(n > 1){
  46.  
  47. 			long long sqrt = getSqrt(n);
  48. 			if(sqrt != -1)ans.pb(sqrt), ans.pb(sqrt);
  49. 			else{
  50.  
  51. 				if(phi == n - 1)ans.pb(n);
  52. 				else{
  53.  
  54. 					long long c = n + 1 - phi, r = getSqrt(c * c - 4 * n);
  55.  
  56. 					long long p1 = (c + r)/2;
  57. 					long long p2 = (c - r)/2;
  58.  
  59. 					if(n%p1 == 0)ans.pb(p1), ans.pb(n/p1);
  60. 					else if(n%p2 == 0)ans.pb(p2), ans.pb(n/p2);
  61.  
  62. 				}	
  63. 			}
  64.  
  65. 		}
  66.  
  67. 		sort(all(ans));
  68. 		printf("%lld", ans[0]);
  69. 		for(int i = 1; i < ans.size(); i++)printf(" %lld", ans[i]);
  70. 		puts("");
  71. 	}
  72. }
  73.  
  74.  
  75.  
  76.  
Success #stdin #stdout 0s 3100KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/o2veMS
language:
C++ (gcc 8.3)
created:
9 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!