D. Common Divisors - 题解

比赛与标签

比赛: Codeforces Round 117 (Div. 2) 标签: brute force, hashing, implementation, math, strings 难度: *1400

喵~ 这是什么神奇问题？

哈罗，各位算法爱好者们，这里是你们最喜欢的小猫娘~ 今天我们要解决一个非常有趣的字符串问题！

题目是这样定义的说：如果字符串 b 可以由字符串 a 重复 x 次（x 是正整数）拼接而成，那么 a 就是 b 的一个 "除数"。比如说，"abab" 就是由 "ab" 重复2次得到的，所以 "ab" 是 "abab" 的一个除数。当然啦，"abab" 自己也是自己的除数（重复1次嘛）。

我们的任务就是，给定两个字符串 s1 和 s2，找出它们共通的 "除数" 有多少个。很简单对吧？喵~

来和喵娘一起探险吧！

一看到这个问题，最直接的想法可能是：把 s1 和 s2 所有可能的除数都找出来，然后看看有多少个是相同的。

一个字符串 t 要是 s 的除数，那 t 肯定得是 s 的一个前缀，并且 s 的长度必须是 t 的长度的整数倍。我们可以遍历所有可能的前缀长度，检查这个前缀重复若干次后是否能构成原字符串。但素！字符串长度最大有 $10^5$ 呢，这样做太暴力了，肯定会超时的说！我们需要更聪明的办法，喵~

让我们换个角度思考！如果一个字符串是由某个更小的部分重复构成的，那这个小部分就是它的周期。比如说，"ababab" 的周期可以是 "ab"，也可以是 "ababab"。其中，最短的那个我们称之为最小周期。对于 "ababab"，它的最小周期就是 "ab"。

这个 "最小周期" 非常关键！我们可以得出一个结论： 一个字符串 s 的所有除数，都必须是由它的最小周期 p 重复若干次构成的！

举个栗子：s = "ababab"，最小周期 p = "ab"。s 的除数只有 "ab" 和 "ababab"。你看，"ab" 是 p 重复1次，"ababab" 是 p 重复3次。是不是很有趣？

那么，对于两个字符串 s1 和 s2：

如果它们想要拥有一个共同的除数，那它们首先必须拥有完全相同的最小周期！就像两块不同的乐高积木，如果基础块都不一样，那肯定拼不出相同的大块呀！
所以，我们第一步就是分别求出 s1 和 s2 的最小周期 p1 和 p2。如果 p1 和 p2 不相等（无论是长度还是内容），那它们就不可能有共同的除数，答案直接就是 0 啦！

那要怎么高效地求一个字符串的最小周期呢？这里就要请出我们的老朋友——KMP算法的 pi 数组（也叫 next 数组）！pi[i] 表示字符串前 i+1 个字符（s[0...i]）的最长公共前后缀的长度。有一个非常神奇的性质：对于长度为 n 的字符串 s，它的 pi 数组最后一个值是 pi[n-1]。

如果 n 可以被 n - pi[n-1] 整除，那么最小周期的长度就是 k = n - pi[n-1]。
否则，这个字符串就不是周期性的，它的最小周期就是它自己，长度为 n。

好啦，现在假设我们已经确认了 s1 和 s2 有着相同的最小周期 p，长度为 k。设 s1 长度为 n1，s2 长度为 n2。那么 s1 就是 p 重复 n1/k 次，s2 就是 p 重复 n2/k 次。

一个共通的除数 t，必然是由 p 重复 m 次构成的，其长度为 m * k。

为了让 t 成为 s1 的除数，n1 必须能被 t 的长度 m * k 整除。
为了让 t 成为 s2 的除数，n2 必须能被 t 的长度 m * k 整除。

也就是说，m * k 必须是 n1 和 n2 的公约数！这意味着，m * k 必须是 gcd(n1, n2) 的约数 (gcd是最大公约数的意思哦)。两边同时除以 k，我们得到：m 必须是 gcd(n1, n2) / k 的约数！

问题瞬间就清晰了！我们要求的共通除数的个数，就等于满足条件的 m 的个数。而 m 的个数，恰好就是 gcd(n1, n2) / k 这个整数的约数个数！

所以，解题步骤就是：

用 KMP 的 pi 数组求出 s1 和 s2 的最小周期长度 k1 和 k2。
比较 s1 的前 k1 个字符和 s2 的前 k2 个字符。如果长度或内容不同，答案为 0。
如果相同，设周期长度为 k = k1。计算 g = gcd(n1, n2)。
计算 target = g / k。
最后，求出 target 这个数有多少个正整数约数，就是最终答案啦！喵~

让魔法代码动起来！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <numeric> // For std::gcd
#include <cmath>   // For std::sqrt

// 这是KMP算法的核心哦，用来计算pi数组，找到前缀和后缀的最长公共部分~
// pi[i] 是 s[0..i] 的最长相等前后缀的长度
std::vector<int> compute_pi(const std::string& s) {
    int n = s.length();
    std::vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        pi[i] = j;
    }
    return pi;
}

// 利用pi数组的魔法性质，找到字符串的最小循环节长度！
// 如果 n % (n - pi[n-1]) == 0，那最小循环节长度就是 n - pi[n-1]
// 否则，它就是非周期性的，循环节就是它自己啦~
int get_smallest_period_len(const std::string& s) {
    int n = s.length();
    if (n == 0) {
        return 0;
    }
    std::vector<int> pi = compute_pi(s);
    int last_pi = pi[n - 1];
    int k = n - last_pi;
    // 如果 n 是 k 的倍数，那么 k 就是最小周期的长度
    if (n % k == 0) {
        return k;
    }
    // 否则，字符串不是周期性的，它的唯一“周期”就是它本身
    return n;
}

// 一个计算正整数约数个数的小助手函数，喵~
// 通过遍历到 sqrt(n) 来高效计算
int count_divisors(int n) {
    if (n <= 0) {
        return 0;
    }
    int count = 0;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            // i 是一个约数
            count++;
            // 如果 i*i != n，那么 n/i 是另一个不同的约数
            if (i * i != n) {
                count++;
            }
        }
    }
    return count;
}

void solve() {
    std::string s1, s2;
    std::cin >> s1 >> s2;

    int n1 = s1.length();
    int n2 = s2.length();

    // 1. 分别找到两个字符串的最小周期长度
    int k1 = get_smallest_period_len(s1);
    int k2 = get_smallest_period_len(s2);

    // 2. 检查它们的最小周期是否完全相同
    // 长度必须相同，并且周期本身（子串）也必须相同
    // 如果它们没有共同的“基因”，就不能有共同的除数
    if (k1 != k2 || s1.compare(0, k1, s2, 0, k1) != 0) {
        std::cout << 0 << std::endl;
        return;
    }

    // 3. 如果周期相同，问题就转化为数论问题啦
    // 设公共最小周期为p，长度为k。
    // 任何公共除数 t 的形式都是 p 重复 m 次。
    // t 的长度 len(t) = m * k
    // len(t) 必须整除 n1 和 n2，所以 len(t) 必须整除 gcd(n1, n2)
    // 即 m*k 必须整除 gcd(n1, n2)
    // 也就是 m 必须整除 gcd(n1, n2) / k
    // 共通除数的个数就等于 m 的可能取值个数
    int g = std::gcd(n1, n2);
    int target = g / k1; // k1 和 k2 相等，用哪个都行

    // 4. 计算 target 的约数个数，就是最终答案！
    std::cout << count_divisors(target) << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

跑得快不快呀？

时间复杂度: O(N1 + N2) 的说。主要的开销在于为 s1 和 s2 计算 pi 数组，这部分的时间复杂度是线性的，也就是 O(n1 + n2)。计算 gcd 非常快，大约是 O(log(min(n1, n2)))。计算约数个数是 O(sqrt(max(n1, n2)))。总的来说，整个算法的瓶颈在于 pi 数组的计算，所以总时间复杂度是 O(n1 + n2)，跑得飞快，完全不用担心的说！
空间复杂度: O(N1 + N2) 的说。我们需要空间来存储 s1 和 s2 的 pi 数组，所以空间复杂度和字符串长度成正比，是 O(n1 + n2)。只需要一点点空间来存放我们的 pi 数组，很省内存的喵~

喵娘的小课堂时间！

今天我们学到了一个超酷的技巧，就是把一个复杂的字符串问题，巧妙地转化成了一个数论问题！

核心思想: 抓住问题的本质——周期性。通过分析字符串的最小重复单元，我们成功地简化了问题。
字符串周期性与KMP: 这是一个黄金组合！一定要记住 pi 数组和字符串最小周期的关系 (k = n - pi[n-1])，这个结论在很多字符串题目里都超级有用！
数论工具: 最大公约数(GCD) 和约数计数在这里扮演了关键角色，它们是连接字符串属性和最终答案的桥梁。

所以呀，下次再遇到看起来很复杂的字符串问题时，不妨想一想它是不是有什么周期性的规律，或者能不能和我们熟悉的数学知识联系起来。多动脑筋，多尝试，你也能成为闪闪发光的算法大师的喵~ 加油哦！

D. Common Divisors - 题解 ​

比赛与标签 ​

喵~ 这是什么神奇问题？ ​

来和喵娘一起探险吧！ ​

让魔法代码动起来！ ​

跑得快不快呀？ ​

喵娘的小课堂时间！ ​