結果

問題 No.3365 Prefix and Suffix X
コンテスト
ユーザー tau1235
提出日時 2025-11-17 22:53:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,219 bytes
コンパイル時間 3,356 ms
コンパイル使用メモリ 285,688 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-11-17 22:54:09
合計ジャッジ時間 22,797 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll=long long;
pair<ll,ll> extgcd(ll a,ll b){
  if (b==0) return {1,0};
  auto [y,x]=extgcd(b,a%b);
  y-=a/b*x;
  return {x,y};
}
ll f(ll a,ll b,ll mod){
  ll g=gcd(gcd(a,b),mod);
  a/=g;
  b/=g;
  mod/=g;
  ll g2=gcd(a,mod);
  if (g2==1) return (extgcd(a,mod).first*b)%mod;
  else return -1;
}

void solve(){
  vector<ll> ten(20);
  ten[0]=1;
  for (int i=1;i<20;i++) ten[i]=ten[i-1]*10;
  string x;
  ll m;
  cin>>x>>m;
  int nx=x.size();
  for (int nz=0;nz+nx*2<=18;nz++){
    ll p=ten[nx+nz]+ten[0];
    ll b=((-p*stoll(x))%m+m)%m;
    ll a=ten[nx];
    ll z=f(a,b,m);
    if (z!=-1){
      string z2=to_string(z);
      if (nz<z2.size()) continue;
      while (nz>z2.size()) z2="0"+z2;
      string ans=x+z2+x;
      cout<<ans<<endl;
      return;
    }
  }
  auto check=[&](string s){
    int n=s.size();
    bool ok=stoll(s)%m==0;
    for (int i=0;i<nx;i++){
      ok&=s[i]==x[i];
      ok&=s[n-nx+i]==x[i];
    }
    return ok;
  };
  for (int i=0;i<nx;i++){
    string ans=x;
    for (int j=i;j<nx;j++) ans+=x[j];
    if (check(ans)){
      cout<<ans<<endl;
      return;
    }
  }
  cout<<-1<<endl;
}

int main(){
  int t;
  cin>>t;
  while (t--) solve();
}
0