結果

問題 No.186 中華風 (Easy)
コンテスト
ユーザー legosuke
提出日時 2019-01-12 04:24:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,203 bytes
コンパイル時間 1,857 ms
コンパイル使用メモリ 172,952 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-14 21:55:39
合計ジャッジ時間 2,489 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21 WA * 2
権限があれば一括ダウンロードができます

ソースコード

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