S老师的公式(最简单）

我这个一定是最简单的解法。

一开始我是被吓了一下的，10^6!的阶乘用计算机根本算不出来

但是我们人类有一门数学这个学科，所以我开始对这个式子进行分析 前面的求和其实就是n*(n + 1） / 2；后面的是n!，这两个式子都含有n，所以我开始分类讨论

当n为奇数时，n + 1就是偶数，所以(n + 1) / 2就是一个整数，且这个整数是小于n的，左边包含了n和(n + 1) / 2，右边也含有n和(n + 1） / 2，所以最大公约数是n * (n + 1) / 2；

当n为偶数时，n / 2就是公因子，最后就是讨论n + 1和2(n - 1)!的公约数，这里我通过试验得出结论是它俩的公约数是n + 1或1，前者是当n + 1不为素数时的情况。（这里就不严格证明了）

下面的图片是当时的思考过程： 下面是代码

#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int x){
    if(x < 3)return x - 1;
    for(int i=2;i<=sqrt(x);++i){
        if(x % i == 0)return false;
    }
    return true;
}
int main(){
    long long n;
    cin >> n;
    long long x = n * (n + 1) / 2;
    if(n > 1 && isPrime(n + 1)){
        cout << n / 2;
    }
    else{
        cout << x;
    }
    return 0;
}