結果

問題 No.187 中華風 (Hard)
コンテスト
ユーザー hos.lyric
提出日時 2019-01-17 18:58:22
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 412 ms / 3,000 ms
コード長 3,665 bytes
コンパイル時間 1,175 ms
コンパイル使用メモリ 125,764 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-13 02:52:36
合計ジャッジ時間 6,698 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


// a^-1 (mod m)
long modInv(long a, long m)
in {
  assert(m > 0, "modInv: m must be positive");
}
do {
  long b = m, x = 1, y = 0, t;
  for (; ; ) {
    t = a / b;
    a -= t * b;
    if (a == 0) {
      assert(b == 1 || b == -1, "modInv: gcd(a, m) != 1");
      if (b == -1) {
        y = -y;
      }
      return (y < 0) ? (y + m) : y;
    }
    x -= t * y;
    t = b / a;
    b -= t * a;
    if (b == 0) {
      assert(a == 1 || a == -1, "modInv: gcd(a, m) != 1");
      if (a == -1) {
        x = -x;
      }
      return (x < 0) ? (x + m) : x;
    }
    y -= t * x;
  }
}

bool allZero;

// Find the smallest x (>= 0) s.t. x == a[i] (mod m[i]), mod m0
//   x = y[0] + m[0] y[1] + m[0] m[1] y[2] + ... + m[0] ... m[n - 1] y[n - 1]
long garner(long[] a, long[] m, long m0)
in {
  foreach (i; 0 .. m.length) {
    assert(0 < m[i] && m[i] <= 0x7fffffff, "garner: 0 < m < 2^31 must hold");
  }
}
do {
  long t;
  auto y = new long[m.length];
  foreach (i; 0 .. m.length) {
    y[i] = a[i] % m[i];
    t = 1;
    foreach (j; 0 .. i) {
      (y[i] -= t * y[j]) %= m[i];
      (t *= m[j]) %= m[i];
    }
    if (((y[i] *= modInv(t, m[i])) %= m[i]) < 0) {
      y[i] += m[i];
    }
  }
  
  // !
  allZero = !y.any;
  
  long x = 0;
  t = 1;
  foreach (i; 0 .. m.length) {
    (x += t * y[i]) %= m0;
    (t *= m[i]) %= m0;
  }
  return x;
}


immutable MO = 10L^^9 + 7;

int N;
long[] X, Y;

long solve() {
  long[] ps;
  foreach (i; 0 .. N) {
    long y = Y[i];
    for (long d = 2; d * d <= y; ++d) {
      if (y % d == 0) {
        ps ~= d;
        for (; (y /= d) % d == 0; ) {}
      }
    }
    if (y > 1) {
      ps ~= y;
    }
  }
  ps = ps.sort.uniq.array;
  debug {
    writeln("ps = ", ps);
  }
  foreach (p; ps) {
    auto pks = new long[N];
    pks[] = 1;
    foreach (i; 0 .. N) {
      long y = Y[i];
      for (; y % p == 0; y /= p) {
        pks[i] *= p;
      }
    }
    const i0 = pks.maxIndex;
    foreach (i; 0 .. N) {
      if (X[i] % pks[i] != X[i0] % pks[i]) {
        return -1;
      }
      if (i != i0) {
        Y[i] /= pks[i];
        X[i] %= Y[i];
      }
    }
  }
  debug {
    writeln("X = ", X);
    writeln("Y = ", Y);
  }
  const res = garner(X, Y, MO);
  if (allZero) {
    long ans = 1;
    foreach (i; 0 .. N) {
      (ans *= Y[i]) %= MO;
    }
    return ans;
  } else {
    return res;
  }
}

void main() {
  try {
    for (; ; ) {
      N = readInt();
      X = new long[N];
      Y = new long[N];
      foreach (i; 0 .. N) {
        X[i] = readLong();
        Y[i] = readLong();
      }
      const ans = solve();
      writeln(ans);
    }
  } catch (EOFException e) {
  }
}
0