Advertisement
Guest User

tortoise, hare and TLE

a guest
Oct 11th, 2014
300
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define LIM 20000000
  4.  
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. ll A,B,C;
  9.  
  10. #define mod(x,y) ((x)  >= (y) || (x) <= -(y) ? (x)%(y) : (x))
  11. #define F(x) mod((A*(x) + mod(x,B)),C)
  12.  
  13. ll floyd(){
  14.     ll tortoise = F(1ll), hare = F(F(1ll));
  15.     while(tortoise != hare){ tortoise = F(tortoise); hare = F(F(hare)); }
  16.     int mu = 0; hare = 1ll;
  17.     while(tortoise != hare && mu <= LIM){
  18.         tortoise = F(tortoise);
  19.         hare = F(hare);
  20.         mu++;
  21.     }
  22.     if(mu > LIM) return -1;
  23.    
  24.     int lambda = 1; hare = F(tortoise);
  25.     while(tortoise != hare && lambda <= LIM){
  26.         hare = F(hare);
  27.         lambda++;
  28.     }
  29.     if(lambda > LIM || lambda + mu > LIM) return -1;
  30.      
  31.     return lambda + mu;
  32. }
  33.  
  34. int main(){
  35.     ios_base::sync_with_stdio(0);
  36.    
  37.     #ifdef ONLINE_JUDGE
  38.     freopen("input.txt", "rb", stdin);
  39.     freopen("output.txt", "w", stdout);
  40.     #endif
  41.    
  42.     while(cin >> A >> B >> C){
  43.         cout << floyd() << '\n';
  44.     }
  45. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement