题目题解

问题理解

定义字符串 $a$ 与正整数 $x$ 的乘法为重复 $x$ 次。
若存在 $x$ 使得 $b \cdot x = a$，则称 $a$ 可被 $b$ 整除。
$\operatorname{LCM}(s, t)$ 是能同时被 $s$ 和 $t$ 整除的最短非空字符串。

给定两个由 'a' 和 'b' 组成的字符串 $s$ 和 $t$，求 $\operatorname{LCM}(s, t)$，若不存在则输出 -1。

第一步：必要条件

设 $n = |s|$，$m = |t|$。
若 $\operatorname{LCM}(s, t)$ 存在，设其长度为 $L$，则 $L$ 必须是 $n$ 和 $m$ 的公倍数。
最小可能的 $L$ 是 $\mathrm{lcm}(n, m) = \frac{n \cdot m}{\gcd(n, m)}$。

因此，$\operatorname{LCM}(s, t)$ 的长度至少为 $\mathrm{lcm}(n, m)$。

第二步：构造候选

将 $s$ 重复 $\frac{m}{\gcd(n, m)}$ 次，得到字符串 $S'$，长度为 $\mathrm{lcm}(n, m)$。
将 $t$ 重复 $\frac{n}{\gcd(n, m)}$ 次，得到字符串 $T'$，长度也为 $\mathrm{lcm}(n, m)$。

若 $S' = T'$，则这个公共字符串就是 $\operatorname{LCM}(s, t)$（因为它的长度最小且能被 $s$ 和 $t$ 整除）。
否则，不存在这样的字符串（因为任何能同时整除 $s$ 和 $t$ 的字符串的长度必须是 $\mathrm{lcm}(n, m)$ 的倍数，而最短的可能长度已经检验，若不相等则不可能）。

第三步：正确性证明

• 若 $\operatorname{LCM}(s, t)$ 存在，其长度必为 $\mathrm{lcm}(n, m)$ 的倍数。取最小倍数 $\mathrm{lcm}(n, m)$，该字符串必须同时是 $s$ 和 $t$ 的重复拼接。由于 $s$ 和 $t$ 本身是周期串，该字符串必然等于 $S'$ 和 $T'$。因此 $S' = T'$。
• 反之，若 $S' = T'$，则该字符串显然能被 $s$ 和 $t$ 整除，且长度最小。

第四步：时间复杂度

• 计算 $\gcd$：$O(\log \min(n, m))$。
• 字符串构造：$O(\mathrm{lcm}(n, m)) \le O(n \cdot m)$，但 $n, m \le 20$，完全可行。

代码实现

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

string mul(const string& s, int k) {
    string res;
    for (int i = 0; i < k; i++) {
        res += s;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        string s, t;
        cin >> s >> t;
        int n = s.size(), m = t.size();
        int g = __gcd(n, m);
        string a = mul(s, m / g);
        string b = mul(t, n / g);
        if (a == b) {
            cout << a << "\n";
        } else {
            cout << "-1\n";
        }
    }
    
    return 0;
}

验证样例

输入：

3
baba
ba
aa
aaa
aba
ab

输出：

baba
aaaaaa
-1

与题目输出一致。

总结

本题的关键在于：

1. 候选字符串长度必须是 $\mathrm{lcm}(|s|, |t|)$。
2. 将 $s$ 和 $t$ 分别重复到该长度，比较是否相等。
3. 若相等，则其为 $\operatorname{LCM}$；否则不存在。