1 solutions
-
0
这是去年暑假牛客上面的一道训练题,首先计算前n个自然数的平方和公式为n(n + 1)(2n + 1)/6,用这个公式用python或者c++去计算几百或者几千项
发现只有1和24是和方数,我们再多打一点,比如打前一万项,前十万项,发现再也没有了,那么我们猜测只有1和24是和方数。所以答案为2。这道题是打表题,也就是说我们要学会去根据题目描述去批量计算,然后根据统计的结果去猜测答案,一般来讲这种需要验证的数字特别大大到离谱的题(超过1e9),一般都是有规律的,打表就可以总结出来,只是有的规律明显,有的规律特别复杂,会涉及到二阶或者三阶差分(这里的差分不是指差分和前缀和算法,而是数学上的差分)。
C++核心参考代码:inline void solve() { int n = 100; for (int i = 1; i <= n; ++i) { long long sqr_s = (i * (i + 1) * (2 * i + 1)) / 6; //注意long long cout << i <<(((long long)(sqrt(sqr_s)) == sqrt(sqr_s)) ? " : Yes\n" : " : No\n"); } }python参考代码:
for i in range(1, 1001): x = i * (i + 1) * (2 * i + 1) / 6 from math import sqrt if sqrt(x) == int(sqrt(x)): print(f"{i} : Yes") else: print(f"{i} : No")答案为2
- 1
Information
- ID
- 15243
- Time
- 60000ms
- Memory
- 256MiB
- Difficulty
- 1
- Tags
- # Submissions
- 17
- Accepted
- 4
- Uploaded By