汪弟弟不会做的数正方形?

发布于 2019-06-07  54 次阅读


题目

  • 我们的李弟弟自从学会了数正方形后,就越发膨胀,所有他出了一道有关正方形的题,来让汪学长做,给一个n*n点,问这些点可以组成多少个正方形?
  • 这种取法皆为合法的!!

输入

  • 输入包含多个测试实例,每个实例包含一个数n(0<n<=1000000),n为0时结束输入。
  • 由于答案有可能过大,取模余1e9+7

输出

  • 对于每个测试实例,输出其的答案,每个实例的输出占一行.

样例输入

  • 4

样例输出

  • 20

找规律

[点数] [组成的正方形] [与上个点数的差值]
[2] 1 [ ]
[3] [6] [5]
[4] [20] [14]
[5] [50] [30]
[6] [105] [55]

得出

下一个点数组成的正方形的差值是当前点数-1的平方加上上一个点数与上上个点数的差值
比如
45的点数的差值是30那么56的差值就是
(6-1)*(6-1)+30 = 55

解题

#include <cstdio>
using namespace std;
long long a[1000010];
int main()
{
    long long tmp;
    a[1] = 0;
    a[2] = 1;
    tmp = 5;
    for(long long i=3;i<=1000000;i++)
    {
        a[i] =a[i-1] + tmp;
        tmp+=i*i;
        a[i]%=1000000007;
    }
     long long n;
    while(~scanf("%lld",&n)&&n)
    {
        printf("%lld\n",a[n]);
    }
}

还是好热爱web开发