S 老师的公式 - 题解

标签与难度

标签: 数论, 最大公约数, gcd, 模运算, 数学, 思维题

难度: 1300

题目大意喵~

S 老师给了我们一个可爱的数学问题，需要我们计算一个公式的值，喵~

这个公式是：

\gcd\left(\sum_{i=1}^{n} i, \prod_{i=1}^{n} i\right)

简单来说，就是求 “从1到n所有整数的和” 与 “从1到n所有整数的积（也就是n的阶乘）” 这两个数的最大公约数（GCD），呐。

输入: 一个整数 $n$ 。输出: 一个整数，表示计算结果。

比如，如果 $n=3$ ，那么：

和是 $1+2+3=6$
积是 $1 \times 2 \times 3 = 6$
$\gcd(6, 6) = 6$ 。

如果 $n=4$ ，那么：

和是 $1+2+3+4=10$
积是 $1 \times 2 \times 3 \times 4 = 24$
$\gcd(10, 24) = 2$ 。

解题思路分析

这道题看起来像一个纯粹的数学题，对吧？我们来一步步把它拆解开，就像猫咪拆毛线球一样，喵~

首先，我们来分析一下公式里的两个部分。

求和部分: $\sum_{i=1}^{n} i$ 这是一个等差数列求和，我们有非常经典的公式可以直接计算，不需要傻乎乎地用循环去加哦！
$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$
我们把这个和记作 $S$ 吧。
求积部分: $\prod_{i=1}^{n} i$ 这个就是 $n$ 的阶乘，记作 $n!$ 。
$\prod_{i=1}^{n} i = 1 \times 2 \times 3 \times \dots \times n = n!$
我们把这个积记作 $F$ 好了。

所以，我们的任务就是计算 $\gcd(S, F)$ ，也就是 $\gcd(\frac{n(n+1)}{2}, n!)$ 。

遇到的第一个小麻烦：数字太大了！

直接计算 $S$ 和 $F$ 然后求 GCD 可以吗？ $S = \frac{n(n+1)}{2}$ 这个还好，即使 $n$ 很大（比如 $10^6$ ）， $S$ 的数量级大约是 $10^{12}$ ，用 long long 存得下。

但是 $F = n!$ 就完全不一样了！阶乘增长得飞快，当 $n=21$ 的时候， $21!$ 就已经超过了 long long 的最大值（大约是 $9 \times 10^{18}$ ）。如果题目给的 $n$ 再大一点，我们根本无法直接计算并存储 $n!$ 的值。怎么办呢，喵？

解决问题的关键魔法：GCD 的性质！

这时候就要请出我们数论中的一个超级好用的性质啦！对于任意正整数 $a$ 和 $b$ ，它们的最大公约数满足：

\gcd(a, b) = \gcd(a, b \pmod a)

其中 $b \pmod a$ 是 $b$ 除以 $a$ 的余数。

这个性质是欧几里得算法（辗转相除法）的核心。它告诉我们，一个数对 $a$ 取模后，并不会改变它与 $a$ 的最大公约数。

利用这个性质，我们的问题 $\gcd(S, F)$ 就可以转化为 $\gcd(S, F \pmod S)$ 。

为什么这个转换是我们的救星？

因为 $F \pmod S$ 的结果一定是一个小于 $S$ 的数！这样我们就完美地避开了计算那个天文数字 $F$ 的难题。我们只需要计算出 $F$ 对 $S$ 取模的结果就行了。

那么，如何计算 $F \pmod S$ 也就是 $n! \pmod S$ 呢？我们可以利用模运算的性质：

(a \times b) \pmod m = ((a \pmod m) \times (b \pmod m)) \pmod m

所以，我们可以迭代计算 $n! \pmod S$ ：

初始化一个变量 factorial_mod_S = 1。
从 $i=1$ 循环到 $n$ 。
在每一步，都更新 factorial_mod_S = (factorial_mod_S * i) % S。这样，在整个计算过程中，我们的中间结果永远不会超过 $S$ 的范围，也就不会溢出了，是不是很巧妙呀？

最终的解题步骤

好啦，现在我们把所有思路整理一下，就得到了清晰的解题步骤：

读入 n: 从输入中获取整数 $n$ 。
计算 S: 使用公式 $S = \frac{n(n+1)}{2}$ 计算出和。记得要用 long long 类型来存储，防止 $n$ 比较大时溢出哦。
计算 F mod S:
- 初始化一个变量 factorial_mod_S 为 1。
- 写一个从 1 到 $n$ 的循环，在循环中不断地将当前循环变量 $i$ 乘到 factorial_mod_S 上，并对 $S$ 取模。
- factorial_mod_S = (factorial_mod_S * i) % S;
- 一个小小的优化: 如果在计算过程中 factorial_mod_S 变成了 0，那么它之后乘以任何数再取模，结果都将是 0。所以一旦它变成 0，我们就可以提前结束循环了。
求最终的 GCD: 计算 $\gcd(S, \text{factorial\_mod\_S})$ 。
输出结果: 把计算出的 GCD 打印出来就大功告成啦，喵~

代码实现

这是我根据上面的思路，精心为你准备的一份代码，注释超详细的哦！

cpp

#include <iostream>
#include <numeric> // C++17 中 gcd 函数在这个头文件里

// 一个标准的辗转相除法求最大公约数 (GCD)
// a 和 b 都是非负整数
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    // 为了更快的输入输出，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    long long n;
    std::cin >> n;

    // 步骤 1: 计算从 1 到 n 的和 S
    // 公式是 S = n * (n + 1) / 2
    // 使用 long long 防止 n 较大时 n * (n + 1) 溢出
    long long sum_val = n * (n + 1) / 2;

    // 如果 sum_val 是 1，那么任何数和 1 的 gcd 都是 1
    // 同时也处理了 n=1 的情况
    if (sum_val == 1) {
        std::cout << 1 << std::endl;
        return 0;
    }

    // 步骤 2: 计算 n! mod sum_val
    // 我们不需要计算 n! 的真实值，只需要计算它对 sum_val 的余数
    long long factorial_mod_sum = 1;
    for (long long i = 1; i <= n; ++i) {
        factorial_mod_sum = (factorial_mod_sum * i) % sum_val;
        // 优化: 如果余数在某个步骤变成了0，
        // 那么后续所有乘法结果对 sum_val 取模后都会是0。
        // 我们可以提前结束循环。
        if (factorial_mod_sum == 0) {
            break; 
        }
    }

    // 步骤 3: 利用 gcd(a, b) = gcd(a, b mod a) 的性质
    // 我们要求 gcd(sum_val, n!)，这等价于求 gcd(sum_val, n! mod sum_val)
    // 如果 factorial_mod_sum 在循环后为 0，说明 sum_val 是 n! 的一个因子。
    // 此时 gcd(sum_val, n!) = sum_val。
    if (factorial_mod_sum == 0) {
        std::cout << sum_val << std::endl;
    } else {
        // 否则，我们计算 gcd(sum_val, factorial_mod_sum)
        std::cout << gcd(sum_val, factorial_mod_sum) << std::endl;
    }

    return 0;
}

复杂度分析

时间复杂度: $O(n)$ 计算 sum_val 是 $O(1)$ 的。计算 factorial_mod_sum 需要一个从 1 到 $n$ 的循环，所以这部分是 $O(n)$ 。最后的 gcd 计算，其时间复杂度大约是 $O(\log(\text{sum\_val}))$ ，因为 sum_val 大约是 $n^2$ 的量级，所以 gcd 复杂度是 $O(\log(n^2)) = O(\log n)$ 。总的时间复杂度由耗时最长的部分决定，也就是那个循环，所以是 $O(n)$ ，呐。
空间复杂度: $O(1)$ 我们只使用了几个变量来存储 n、sum_val 和 factorial_mod_sum 等，没有使用额外的、随输入规模 $n$ 变化的存储空间。所以空间复杂度是常数级别的，也就是 $O(1)$ 。

知识点总结

通过解决这道题，我们又掌握了一些有用的知识呢，喵~

等差数列求和公式: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ ，这是一个必须牢记于心的小工具！
GCD 的重要性质: $\gcd(a, b) = \gcd(a, b \pmod a)$ 。这个性质是解决许多与 GCD 和大数相关的数论问题的金钥匙。
模运算处理大数: 当遇到像阶乘这样会快速增长到溢出的数字时，如果最终运算只关心它对某个数的余数，就可以全程使用模运算来控制中间结果的大小。
数据类型选择: 在编程竞赛中，要时刻对数字的范围保持敏感，选择合适的据类型（比如 long long）来防止溢出，这是一个好习惯的说。

希望这篇题解能帮到你，如果还有问题，随时可以再来问我哦！喵~

S 老师的公式 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

遇到的第一个小麻烦：数字太大了！ ​

解决问题的关键魔法：GCD 的性质！ ​

为什么这个转换是我们的救星？ ​

最终的解题步骤 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​