博客

这题刚开始自己推的公式，

假设的是三个数位想x,x+a,x+b，

得出x>b-a，即俩个较大的数之差小于最小数，

根据这个关系推出，

代码中的公式，本人不善表达，可以自行理解：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#define LL long long
using namespace std;
const int N=1e6+5;
int main()
{
    int n;
    while(cin>>n)
    {
        if(n<3) break;
        LL sum=0;
        for(LL i=1;2*i+1<=n;i++)
            sum=sum+((n-2*i-1)*(n-2*i-1)+(n-2*i-1))/2;
        printf("%lld\n",sum);
    }
    return 0;
}

但是书上使用的方式和我的不一样，而且书上使用了预处理，当然比我的快的多，可以自行参考大白书107页：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1e6+10;
LL f[1000010];
int main()
{
    f[3]=0;
    for(LL x=4;x<=1000000;x++)
        f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;
    int n;
    while(cin>>n)
    {
        if(n<3) break;
        printf("%lld\n",f[n]);
    }
    return 0;
}