結果

問題 No.3365 Prefix and Suffix X
コンテスト
ユーザー kotatsugame
提出日時 2025-11-17 22:44:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 487 ms / 2,000 ms
コード長 1,073 bytes
コンパイル時間 755 ms
コンパイル使用メモリ 81,020 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-11-17 22:45:15
合計ジャッジ時間 17,642 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cassert>
#include<atcoder/math>
using namespace std;
string X;
int M;
long p10[20];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;cin>>T;
	for(;T--;)
	{
		cin>>X>>M;
		string ans="-1";
		for(int len=X.size();len<=18;len++)
		{
			if(len<=X.size()*2)
			{
				string Y(len,'0');
				for(int i=0;i<X.size();i++)
				{
					Y[i]=X[i];
					Y[len-X.size()+i]=X[i];
				}
				if(Y.substr(0,X.size())!=X||Y.substr(len-X.size())!=X)continue;
				int y=0;
				for(char v:Y)y=y*10+v-'0';
				if(y%M==0)
				{
					ans=Y;
					break;
				}
				continue;
			}
			p10[0]=1%M;
			for(int i=0;i<len;i++)p10[i+1]=p10[i]*10%M;
			long need=0;
			for(int i=0;i<X.size();i++)need-=(p10[len-i-1]+p10[X.size()-i-1])*(X[i]-'0');
			need=(need%M+M)%M;
			auto z=atcoder::internal::inv_gcd(p10[X.size()],M);
			if(need%z.first!=0)continue;
			need/=z.first;
			string Y=to_string((long)need*z.second%M);
			if(Y.size()>len-2*X.size())continue;
			while(Y.size()<len-2*X.size())Y="0"+Y;
			Y=X+Y+X;
			ans=Y;
			break;
		}
		cout<<ans<<"\n";
	}
}
0