Educational Codeforces Round 102 (Rated for Div. 2) B. String LCM (构造,思维)

题意:给你两个字符串\(a\)和\(b\),找出它们的\(lcm\),即构造一个新的字符串\(c\),使得\(c\)可以由\(x\)个\(a\)得到,并且可以由\(y\)个\(b\)得到,输出\(c\),如果\(c\)不存在,输出\(-1\).
题解:我们可以根据\(a\)和\(b\)的长度得出\(c\)的长度\(len_c\),而\(len_c\)一定是\(len_a\)和\(len_b\)的倍数, 我们就可以根据这个倍数关系构造出\(c\)(用\(a\)或者\(b\)构造都行,因为假如合法的话,它们两个一定都是满足的),然后跑个循环check一下就好了.
代码:

#include <bits/stdc++.h>

#define ll long long

#define fi first

#define se second

#define pb push_back

#define me memset

#define rep(a,b,c) for(int a=b;a<=c;++a)

#define per(a,b,c) for(int a=b;a>=c;--a)

const int N = 1e6 + 10;

const int mod = 1e9 + 7;

const int INF = 0x3f3f3f3f;

using namespace std;

typedef pair<int,int> PII;

typedef pair<ll,ll> PLL;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

int __;

string s,t;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>__;

	while(__--){

		cin>>s>>t;

		int len1=(int)s.size();

		int len2=(int)t.size();

		if(len1<len2){

			swap(s,t);

			swap(len1,len2);

		}

		int cur=lcm(len1,len2)/len2;

		string tmp="";

		rep(i,1,cur){

			tmp+=t;

		}

		bool flag=true;

		int i=0;

		while(i<(int)tmp.size()){

			rep(j,0,len1-1){

				if(tmp[i]!=s[j]){

					flag=false;

					break;

				}

				i++;

			}

			if(!flag) break;

		}

		if(flag) cout<<tmp<<'\n';

		else cout<<"-1\n";

	}

    return 0;

}

巴特西

Educational Codeforces Round 102 (Rated for Div. 2) B. String LCM (构造,思维)

最新文章

热门文章