AOJ0114 Electro-Fly

問題  電子蝿 | Aizu Online Judge

考察:

とりあえずの各座標について1 -> 1になるまでの移動回数を求めたい

式に注目すると

（はじめは）

...

といったようにが再帰的に求められることがわかる. 

移動回数を求めるには木の深さを求める要領でとなるまで繰り返す

について移動回数を求め, 最小公倍数を求めればよい

コード

#include <iostream>
using namespace std;
using ll = long long;

ll min_cost(ll n, ll a1, ll m1) { 
    if (n == 1) return 1; 
    return 1 + min_cost(n*a1%m1,a1, m1);
}
ll gcd(ll a, ll b) { 
    if (b == 0) return a; 
    return gcd(b, a%b);
}
int main() { 
    ll a1, m1, a2, m2, a3, m3; 
    while (cin >> a1 >> m1 >> a2 >> m2 >> a3 >> m3) { 
        if (a1 == 0 && m1 == 0 && a2 == 0 && m2 == 0 && a3 == 0 && m3 == 0) break;
        ll l1 = min_cost(a1%m1, a1, m1); 
        ll l2 = min_cost(a2%m2, a2, m2); 
        ll l3 = min_cost(a3%m3, a3, m3);
        ll L1 = l1/gcd(l1, l2)*l2;
        cout << L1 * l3 / gcd(L1, l3) << endl; 
    }
    return 0;
}