結果

問題 No.186 中華風 (Easy)
ユーザー tubo28tubo28
提出日時 2015-10-23 20:20:19
言語 C++11
(gcc 11.4.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,408 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 57,216 KB
最終ジャッジ日時 2023-09-27 00:48:09
合計ジャッジ時間 745 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ（β）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
main.cpp:39:19: error: ‘std::pair<__int128, __int128> crt’ redeclared as different kind of symbol
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                   ^~~~~~
main.cpp:12:15: note: previous declaration ‘std::pair<__int128, __int128> crt(lll, lll, lll, lll)’
 pair<lll,lll> crt(lll a1, lll m1, lll a2, lll m2){
               ^~~
main.cpp:39:19: error: ‘vector’ was not declared in this scope
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                   ^~~~~~
main.cpp:39:19: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
main.cpp:6:1:
+#include <vector>
 using namespace std;
main.cpp:39:19:
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                   ^~~~~~
main.cpp:39:29: error: expected primary-expression before ‘>’ token
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                             ^
main.cpp:39:31: error: ‘a’ was not declared in this scope
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                               ^
main.cpp:39:34: error: ‘vector’ was not declared in this scope
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                                  ^~~~~~
main.cpp:39:34: note: ‘std::vector’ is defined in header ‘<vector>’; did you forget to ‘#include <vector>’?
main.cpp:39:44: error: expected primary-expression before ‘>’ token
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                                            ^
main.cpp:39:46: error: ‘m’ was not declared in this scope
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                                              ^
main.cpp:39:46: note: suggested alternative: ‘tm’
 pair<lll,lll> crt(vector<lll> a, vector<lll> m){
                                              ^
                                              tm
main.cpp: In function ‘int main()’:
main.cpp:52:5: error: ‘vector’ was not declared in this scope
     vector<lll> x(n), y(n)

ソースコード

diff # 

#include <iostream>
#include <cassert>
#include <tuple>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef __int128_t lll;

// x, mod
pair<lll,lll> crt(lll a1, lll m1, lll a2, lll m2){
  auto myabs = [](lll x){ return x > -x ? x : -x; };
  auto mul = [&myabs](lll a, lll b, lll m){
    a = a < 0 ? m - myabs(a)%m : a % m;
    b = b < 0 ? m - myabs(b)%m : b % m;
    return a*b%m;
  };
  auto extgcd = [](lll a, lll b, lll &x, lll &y) {
    for (lll u = y = 1, v = x = 0; a; ) {
      lll q = b / a;
      swap(x -= q * u, u);
      swap(y -= q * v, v);
      swap(b -= q * a, a);
    }
    return b;
  };
  lll k1,k2;
  lll g = extgcd(m1,m2,k1,k2);
  if(myabs(a1-a2)%g != 0){
    return make_pair(-1,-1);
  } else {
    lll l = m1 / g * m2;
    lll x = a1 + mul(mul((a2 - a1) / g, k1, l) , m1, l);
    return make_pair(x,l);
  }
}

pair<lll,lll> crt(vector<lll> a, vector<lll> m){
  lll mod = 1, ans = 0;
  int n = a.size();
  for(int i = 0; i < n; i++){
    tie(ans,mod) = crt(ans, mod, a[i], m[i]);
    if(ans == -1) return make_pair(-1,-1);
  }
  return make_pair(ans,mod);
}

int main(){
  int n = 3;
  while(1){
    vector<lll> x(n), y(n);
    for(int i = 0; i < n; i++){
      ll xx,yy;
      if(!(cin >> xx >> yy)) exit(0);
      x[i] = xx, y[i] = yy;
    }
    lll ans,m;
    tie(ans,m) = crt(x,y);
    if(ans == 0) ans = m;
    cout << (ll)ans << endl;
  }
}
0