fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define endl '\n'
  6. #define fi first
  7. #define se second
  8. #define vall(a) (a).begin(), (a).end()
  9. #define sze(a) (int)a.size()
  10. #define pii pair<int, int>
  11.  
  12. #define pb push_back
  13. #define pf push_front
  14.  
  15.  
  16. const signed N = 5e6 + 5;
  17. const ll oo = 1e18;
  18.  
  19. ll a, b, m, check, t;
  20.  
  21. ll binpow(ll a, ll b, ll mod) {
  22. 	ll res = 1;
  23.     a %= mod;
  24. 	while(b > 0) {
  25. 		if (b & 1) res = (res * a) % mod;
  26. 		a = (a * a) % mod;
  27. 		b >>= 1ll;
  28. 	}
  29. 	return res % mod;
  30. }
  31. ll fcycle() {
  32. 	ll pre = 0, cur = 1;
  33. 	for (int i = 1; i <= m * m; ++i) {
  34. 		ll temp = cur;
  35. 		cur = (pre + cur) % m; pre = temp; 
  36. 		if (cur == 1 && pre == 0) return i;
  37. 	}
  38. 	return 0;
  39. }
  40.  
  41. ll f[N];
  42. void output() {
  43. 	ll du = fcycle();
  44. 	f[1] = 1;
  45. 	for (int i = 2; i <= du; ++i) f[i] = (f[i - 1] + f[i - 2]) % m;
  46.  
  47. 	ll gcd = __gcd(a, b) % du;
  48. 	cout << f[binpow(a, b, du)] << " " << f[gcd]; 
  49.     return;
  50. }
  51.  
  52. void input() {
  53. 	cin >> a >> b >> m;
  54.     output();
  55.     return;
  56. }
  57.  
  58. signed main () {
  59.     if(fopen("", "r")) {
  60.         freopen("", "r", stdin);
  61.         freopen("", "w", stdout);
  62.     }
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(nullptr); cout.tie(nullptr);
  65.     cin >> t;
  66.     while(t--) input();
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
2
3298329 1220121 10
329832929182192 12201919121 100
stdout
copy 
4 479 1
https://ideone.com/YUvybO
language:
C++14 (gcc 8.3)
created:
3 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!