📝 题目大意

给定 $N$（$2 \leq N \leq 30$），求一个在 $N$ 以上且不超过 $10^{13}$ 的整数，使得它对 $2, 3, \ldots, N$ 中的每一个数取模的结果都是 $1$。

💡 解题思路

1. 题目分析：题目要求找到一个数 $X$，使得 $X \bmod k = 1$ 对所有 $k \in [2, N]$ 成立。等价于 $X - 1$ 能被 $2, 3, \ldots, N$ 中的每一个数整除，即 $X - 1$ 是 $2, 3, \ldots, N$ 的公倍数。最小的正整数 $X$ 就是 $\mathrm{lcm}(2, 3, \ldots, N) + 1$。

2. 算法推导：由于 $N \leq 30$，我们可以直接迭代计算 $2$ 到 $N$ 的最小公倍数。设 ans 为当前累计的 LCM，初始值 ans = 2（对应 $k=2$）。然后从 $i=3$ 到 $N$ 遍历，每次用公式 $\mathrm{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$ 更新 ans = lcm(ans, i)。最终输出 ans + 1。

   为什么这样得到的答案一定满足 $\leq 10^{13}$？因为 $N \leq 30$ 时，$\mathrm{lcm}(2, 3, \ldots, 30) \approx 2.33 \times 10^{12}$，加 $1$ 后仍远小于 $10^{13}$，题目保证答案存在。

3. 边界与细节：

   • $N=2$ 时，LCM 为 $2$，答案为 $3$（$3 \bmod 2 = 1$），符合条件。
   • 乘法时使用 1ll 强制转为 long long，避免 int 溢出。虽然 $N$ 很小，但中间 LCM 会迅速增长到 $10^{12}$ 级别，必须用 64 位整数。
   • 使用 __gcd 求最大公约数（GNU 内置函数），无需手写。

⏱️ 复杂度分析

• 时间复杂度：$O(N \log M)$，其中 $M$ 为过程中出现的最大数值。每次迭代做一次 $\gcd$ 运算，$\gcd$ 的复杂度为 $O(\log M)$，共 $N-1$ 次迭代。
• 空间复杂度：$O(1)$，只使用了常数个变量。

💻 标准代码 (C++)

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

// 快速读入整数
void read(ll& x){
    char ch=getchar();
    ll f=1;x=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-48;
        ch=getchar();
    }
    x=x*f;
}

ll N;

// 计算两个数的最小公倍数，注意 1ll 防止乘法溢出
ll lcm(ll A,ll B){
    return A*1ll*B/__gcd(A,B);
}

int main(){
    read(N);
    ll ans=2;                      // 初始 LCM = 2
    // 从 3 到 N 迭代，累积计算 LCM(2, 3, ..., N)
    for(int i=3;i<=N;i++)
        ans=lcm(ans,i);
    cout<<ans+1;                   // 输出 LCM + 1
    return 0;
}