题解 | #S 老师的公式#

读完题目又看了半天，终于理解了，于是写下代码

from math import gcd, factorial

num = int(input())

print(gcd(num * (num + 1) // 2, factorial(num)))

一提交...超时 尝试了加cache，一样超时

于是在本地慢慢调试

最终终于找到了...规律

num 是否质数 gcd结果
4047 False 8191128
4048 False 2024
4049 True 8199225
4050 False 2025
4051 True 8207326
4052 False 8211378
4053 False 8215431
4054 False 8219485
4055 False 8223540
4056 False 2028
4057 True 8231653
4058 False 8235711
4059 False 8239770

发现值只可能为num // 2或num * (num + 1) // 2

还有当num+1为质数时，最终结果为num//2，其余情况值为num * (num + 1) // 2

num = int(input())

def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

if isPrime(num + 1):
    print(num // 2)
else:
    print(num * (num + 1) // 2)

写完这题后，时间只剩半小时了，，，最终就做出这一题...