1 solutions

  • 0
    @ 2024-1-9 14:58:16

    这是去年暑假牛客上面的一道训练题,首先计算前n个自然数的平方和公式为n(n + 1)(2n + 1)/6,用这个公式用python或者c++去计算几百或者几千项image 发现只有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

    Information

    ID
    15243
    Time
    60000ms
    Memory
    256MiB
    Difficulty
    1
    Tags
    # Submissions
    17
    Accepted
    4
    Uploaded By