 # PhonePe2020C

Oct 7th, 2020 (edited)
425
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2. Author: Mehul Chaturvedi
3. */
4.
5. #include <bits/stdc++.h>
6. using namespace std;
7.
8. using ll = long long;
9. #define vll vector<long long>
10. #define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
11.
12. /*
13. * x and y are <= 1e12, that means the count of their parent+parent's parent + .... + root
14. * is less than equal to log_N(1e12) <= 40. So we can store the ancestors of both the vertices
15. * till, the root(0). And check what part is common from the end between both of them. If
16. * we remove that common part then, the remaining elements' count will be the answer
17.
18. * Also, it can easily be seen that the child of the node named i are : in+1, in+2...in+n
19. * So the parent of the node j will be (j-1)/n. (0 based index)
20. */
21.
22. ll n, x, y;
23. void solve() {
24.     cin >> n >> x >> y;
25.     x--; y--;
26.
27.     if (x < y) swap(x, y);
28.     //X is the greater one now
29.
30.     ll parx = x;
31.     ll pary = y;
32.
33.     vll a, b;
34.     bool flaga = 0, flagb = 0;
35.     while (1) {
36.         if (!flaga) {
37.             a.push_back(parx);
38.             if (parx == 0) flaga = 1;
39.         }
40.         if (!flagb) {
41.             b.push_back(pary);
42.             if (pary == 0) flagb = 1;
43.         }
44.
45.         parx = (parx - 1) / n;
46.         pary = (pary - 1) / n;
47.
48.         if (flaga && flagb) break;
49.     }
50.
51.
52.     ll i = a.size() - 1;
53.     ll j = b.size() - 1;
54.
55.     while (1) {
56.         if (a[i] != b[j]) {
57.             cout << i + j + 2 << '\n';
58.             return;
59.         }
60.         i--;
61.         j--;
62.     }
63.
64.     return;
65.
66.
67. }
68.
69. int main(int argc , char ** argv) {
70.     ios_base::sync_with_stdio(false) ;
71.     cin.tie(NULL) ;
72.
73.     ll t = 1;
74.     while (t--) {
75.         solve();
76.     }
77.
78.     return 0 ;
79. }
RAW Paste Data