結果

問題 No.186 中華風 (Easy)
ユーザー legosuke
提出日時 2019-01-12 04:24:56
言語 C++14
(gcc 8.2.0)
結果
WA   .
実行時間 -
コード長 2,203 Byte
コンパイル時間 1,722 ms
使用メモリ 1,540 KB
最終ジャッジ日時 2019-02-23 23:15:37

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
0.in AC 4 ms
1,532 KB
1.in AC 4 ms
1,532 KB
2.in AC 4 ms
1,536 KB
3.in AC 4 ms
1,540 KB
4.in AC 4 ms
1,536 KB
5.in AC 4 ms
1,536 KB
6.in AC 4 ms
1,536 KB
7.in AC 3 ms
1,532 KB
8.in AC 4 ms
1,532 KB
9.in AC 2 ms
1,536 KB
A.in AC 4 ms
1,536 KB
B.in AC 4 ms
1,532 KB
C.in AC 4 ms
1,532 KB
D.in AC 4 ms
1,532 KB
E.in AC 2 ms
1,536 KB
F.in WA -
G.in WA -
system_test1.txt AC 4 ms
1,536 KB
system_test2.txt AC 4 ms
1,532 KB
system_test3.txt AC 4 ms
1,532 KB
system_test4.txt AC 4 ms
1,532 KB
system_test5.txt AC 4 ms
1,532 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EMP emplace
#define EMPB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
#define Bit(n) (1LL << (n))
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

int gcd(int a,int b) { return b?gcd(b,a%b):a; }
int ext_gcd(int a,int b,int& x,int& y) {
  if(b==0){
    x=1;y=0;return a;
  }
  int q=a/b;
  int g=ext_gcd(b,a-q*b,x,y);
  int z=x-q*y;
  x=y;y=z;
  return g;
}
int inv_mod(int a,int m) {
  int x,y;
  ext_gcd(a,m,x,y);
  x%=m;
  return (m+x%m)%m;
}
pair<int, int> linear_congruence(const vector<int>& A, const vector<int>& B, const vector<int>& M) {
  int x = 0, m = 1;
  for (int i = 0; i < A.size(); i++) {
    int a = A[i] * m, b = B[i] - A[i] * x, d = gcd(M[i], a);
    if (b % d != 0) return make_pair(0, -1);
    int t = b / d * inv_mod(a / d, M[i] / d) % (M[i] / d);
    x = x + m * t;
    m *= M[i] / d;
  }
  return make_pair((m + x % m) % m, m);
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  vector<int> A, B, M;
  REP(i, 3) {
    int X, Y;
    cin >> X >> Y;
    for (int p = 2; p*p <= Y; p++) {
      int tmp = 1;
      while (Y % p == 0) {
        Y /= p;
        tmp *= p;
      }
      if (tmp != 1) {
        A.PB(1);
        B.PB(X%tmp);
        M.PB(tmp);
      }
    }
    if (Y != 1) {
      A.PB(1);
      B.PB(X%Y);
      M.PB(Y);
    }
  }
  auto p = linear_congruence(A, B, M);
  if (p.second < 0) cout << -1 << endl;
  else cout << p.first << endl;

  return 0;
}
0