33OJ
登录 注册

1 条题解

  • 1
    @ 2026-11-15 20:15:34

    对于 n=0n=0 的情况,1∣0!=11 | 0!=1,成立。

    对于 n≤4n \le 4 且 n>0n \gt 0 的情况,通过枚举发现:全都不行。

    考虑 nn 是否为质数且 n≥5n \ge 5 的时候。 当 n+1n+1 为质数的时候,由于 n+1n+1 是质数,所以 n+1∣n!n+1|n! 等价于 存在一个 1≤i≤n1 \le i \le n,使得 n+1∣in+1|i,这显然是不可能的。

    当 n+1n+1 为合数的时候

    • 若 n+1n+1 不为完全平方数,则取 n+1n+1 的任意两个因数,设为 p,qp,q,且 p≤qp \le q,那么 q≤n+12≤nq \le \frac{n+1}{2} \le n。所以成立。
    • 若 n+1n+1 为完全平方数的时候,取 p=np=\sqrt{n},那么取 p,2pp,2p 即可,且 2p=2n≤n2p = 2 \sqrt{n} \le n。所以成立。

    综上所述。有:

    • n=0n=0 输出 : Yes。
    • n=1,2,3,4n=1,2,3,4 输出 : No
    • n≥5n \ge 5 且 n+1n+1 为质数 输出 : No
    • n≥5n \ge 5 且 n+1n+1 为合数 输出 : No

    提示:输出 Yes 可获得 88pts。

    #include <bits/stdc++.h>
    
    using namespace std;
    
    bool check(int x) {
        // x >= 6 不需要特判
        for (int i = 2; i <= sqrt(x); i++)
            if (x % i == 0)
                return false;
        return true;
    }
    int main() {
        int x;
        cin >> x;
        if (x == 0) cout << "Yes";
        if (x <= 4 && x != 0) cout << "No";
        if (x >= 5 && check(x + 1) == false) cout << "Yes";
        if (x >= 5 && check(x + 1) == true) cout << "No";
        return 0;
    }
    

    信息

    ID
    74
    时间
    1000ms
    内存
    256MiB
    难度
    显示难度普及
    标签
    (无)
    递交数
    21
    已通过
    2
    上传者