0114:Electro-Fly

戻り蝿のデータを入力とし、(1,1,1)に戻ってくる最小の移動回数を求める問題。

x,y,zがそれぞれ何回の移動回数で1に戻ってくるかを求め、
その3つの最小公倍数が答えとなる。

#include<iostream>
#include<vector>
#include<algorithm>

typedef long long ll;

using namespace std;

ll gcd(ll a,ll b){
  if(b==0)return a;
  return gcd(b, a%b);
}

ll lcm(ll a,ll b){
  return a*b/gcd(a,b);
}

ll lcm_n(vector<ll> num){
  ll l=num[0];
  for(int i=0;i<num.size();i++)l=lcm(l,num[i]);
  return l;
}

ll func(ll a, ll m){
  ll cnt=1,x=a%m;
  while(x!=1)x=(a*x)%m,cnt++;
  return cnt;
}

int main(void){

  ll m[4],a[4];

  while(true){

    int b=0;
    for(int i=1;i<4;i++){
      cin >> a[i] >> m[i];
      b|=a[i]|m[i];
    }
    if(!b)break;
    
    ll cnt=0,x=1,y=1,z=1;
    vector<ll>num;

    for(int i=1;i<4;i++)
    num.push_back(func(a[i],m[i]));

    cout << lcm_n(num) << endl;
  }

  return 0;
}