結果

問題 No.186 中華風 (Easy)
ユーザー beetbeet
提出日時 2019-10-25 17:36:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,364 bytes
コンパイル時間 2,521 ms
コンパイル使用メモリ 207,812 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-20 05:35:09
合計ジャッジ時間 3,572 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 2 ms
6,940 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int DDCC2018QUALB_D()':
main.cpp:83:11: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   83 |   int LIM(1e12);
      |           ^~~~

ソースコード

diff # 

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
#endif
//BEGIN CUT HERE
template<typename T>
T extgcd(T a,T b,T& x,T& y){
  T d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}

template<typename T>
T mod_inverse(T a,T mod){
  T x,y;
  extgcd(a,mod,x,y);
  return (x%mod+mod)%mod;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#undef call_from_test

#endif
//BEGIN CUT HERE
template<typename T>
pair<T, T> linear_congruence(const vector<T> &A,
                             const vector<T> &B,
                             const vector<T> &M){
  T x=0,m=1;
  for(int i=0;i<(int)A.size();i++){
    T a=A[i]*m,b=B[i]-A[i]*x,d=__gcd(M[i],a);
    if(b%d!=0) return make_pair(0,-1);
    T t=b/d*mod_inverse(a/d,M[i]/d)%(M[i]/d);
    x=x+m*t;
    m*=M[i]/d;
  }
  return make_pair((x%m+m)%m,m);
}
//END CUT HERE
#ifndef call_from_test

int is_prime(int x){
  if(x<=1) return 0;
  for(int i=2;i*i<=x;i++)
    if(x%i==0) return 0;
  return 1;
}

signed DDCC2018QUALB_D(){
  const int n = 30;
  vector<int> A,B,M;

  vector<int> x(n+1);
  for(int i=2;i<=n;i++){
    cin>>x[i];
    if(!is_prime(i-1)) continue;
    A.emplace_back(1);
    B.emplace_back(x[i]%(i-1));
    M.emplace_back(i-1);
  }
  auto p=linear_congruence(A,B,M);
  if(p.second<int(0)){
    cout<<"invalid"s<<endl;
    return 0;
  }
  int LIM(1e12);
  int res=p.first,dif=p.second;
  while(res<=LIM){
    int flg=1;
    for(int i=2;i<=n;i++){
      int sum=0,tmp=res;
      while(tmp>int(0)){
        sum+=tmp%i;
        tmp/=int(i);
      }
      flg&=(sum==x[i]);
    }
    if(flg){
      cout<<res<<endl;
      return 0;
    }
    res+=dif;
  }
  cout<<"invalid"s<<endl;
  return 0;
}
/*
   verified on 2019/10/08
   https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d
*/

signed YUKI_186(){
  vector<int> A(3,1),B(3),M(3);
  for(int i=0;i<3;i++) cin>>B[i]>>M[i];
  auto p=linear_congruence(A,B,M);
  if(p.second==-1) cout<<-1<<endl;
  else cout<<(p.first?p.first:p.second)<<endl;
  return 0;
}
/*
   verified on 2019/10/08
   https://yukicoder.me/problems/no/186
*/

//INSERT ABOVE HERE
signed main(){
  //DDCC2018QUALB_D();
  YUKI_186();
  return 0;
}
#endif
0