傳送門
兩個字串 a a a和 b b b,把 a a a看成比較短的那個,長度分別為 n 1 , n 2 n_1,n_2 n1?,n2?
那么毫無疑問,答案必然是 x a xa xa,其中 x x x未知
因為只有這樣能被 a a a整除
而且有 x ? n 1 < = n 1 ? n 2 x*n_1<=n_1*n_2 x?n1?<=n1??n2?
如果 n 1 ? n 2 n_1*n_2 n1??n2?湊不成就不可能湊成
因為每次添加一個 a a a都相當于回圈節往后移動一位, n 1 ? n 2 n_1*n_2 n1??n2?移動了 n 2 n_2 n2?位
再移動下去,就又變成最開始的情況,所以無解，
所以暴力列舉 x x x判斷即可
#include <bits/stdc++.h>
using namespace std;
int id,n1,n2;
string a,b;
char c[10009];
bool isok()
{
if( id%n2!=0 ) return false;
int now = 0;
for(int i=1;i<=id;i++)
{
if( b[now]!=c[i] ) return false;
now++;
if( now==n2 ) now = 0;
}
return true;
}
int main()
{
int t; cin >> t;
while( t-- )
{
cin >> a >> b;
if( a.length()>b.length() ) swap(a,b);
n1 = a.length(), n2 = b.length();
id = 0; int flag = 0;
while( id<=n1*n2 )
{
for(int i=0;i<n1;i++) c[++id] = a[i];
if( isok() ) { flag = 1; break; }
}
if( flag==0 ) { printf("-1\n"); continue; }
for(int i=1;i<=id;i++) printf("%c",c[i]);
printf("\n");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249552.html
標籤：其他
下一篇：原來還有這么通俗易懂的貪吃蛇寫法