数学関連

// 最大公約数
long long gcd(long long a, long long b){
  return b == 0LL ? a : gcd(b, a % b);
}

// 最小公倍数
long long lcm(long long a, long long b){
  return a / gcd(a, b) * b;
}

// 拡張ユークリッドの互除法 gはgcd(a,b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
  long long g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

//連立線形合同式
// a1*x=b1(mod m1)
// a2*x=b2(mod m2)
// a3*x=b3(mod m3)
//
// 以上を満たすようなxをb(mod m)の形で求めます。
// オーバーフローに気をつけましょう。
pair<long long,long long> linear_c(vector<long long> &a, vector<long long> &b, vector<long long> &m){
  long long x = 0;
  long long M = 1;
  for(long long i = 0; i < a.size(); i++){
    long long A = a[i]*M;
    long long B = b[i]-a[i]*x;
    long long D = gcd(m[i],A);
    if(B%D!=0)return make_pair(0,-1);
    long long E = m[i]/D;
    long long X,Y;
    extgcd(A/D,E,X,Y);
    long long T = B/D*((E+X%E)%E)%E;
    x = x+M*T;
    M*=E;
  }
  return make_pair(x%M,M);
}

// 約数の列挙（20 のとき 1 20 2 10 4 5）
vector<long long> divisor(long long n){
  vector<long long> ret;

  for(long long i = 1LL; i * i <= n; i++){
    if(n % i == 0LL){
      ret.push_back(i);
      if(i != n / i){
        ret.push_back(n / i);
      }
    }
  }
  return ret;
}