Educational Codeforces Round 102 (Rated for Div. 2) B. String LCM (构造,思维)
阅读原文时间:2023年07月09日阅读:2

  • 题意:给你两个字符串\(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
    #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 PII;
    typedef pair 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&lt;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&lt;(int)tmp.size()){
        rep(j,0,len1-1){
            if(tmp[i]!=s[j]){
                flag=false;
                break;
            }
            i++;
        }
        if(!flag) break;
    }
    
    if(flag) cout&lt;&lt;tmp&lt;&lt;'\n';
    else cout&lt;&lt;"-1\n";
    } return 0;

    }