HackerRank October Challenge 2013 Editorial [Period] ________________By: Nafis Sadique

Problem: Period
The problem asks to find out n such that for given a, b, m
( (a + b√5)^n ) % m = 1
If no n is found then you have to output -1.

Observation:
Now lets find out the first k for which
((a + b√5)^k) % m = p, p is an integer.
Then   ((a + b√5)^tk) % m = q, q is an integer.

We also can figure out that k < m & t < m. So we can traverse for the value of k. Then We can traverse again for the value of t such that q = 1. After that we have to print tk.

Code:

1. cin >> T;
2. while(T--){
3. cin >> a >> b >> m;
4. c = 1, d = 0;
5. int period = 0;
6. REP(i, m + 10){
7. x = (a * c + 5ll * b * d) % m;
8. y = (a * d + b * c) % m;
9. c = x; d = y;
10. if(d == 0){
11. period = i + 1;
12. break;
13. }
14. }
15. LL tmp = c, fin = 0;
16. e = 1;
17. REP(i, m + 10){
18. e *= tmp;
19. e %= m;
20. if(e == 1){
21. fin = (i + 1) * period;
22. break;
23. }
24. }
25. if(fin == 0)cout << -1 << endl;
26. else cout << fin << endl;
27. }