821B - Okabe and Banana Trees——数学公式-蒲公英云

821B - Okabe and Banana Trees——数学公式

Think:
1题意：沿着一条线段这里写图片描述，在这条线段下点可在线段上，找一个矩形，矩形的边分别与x轴，y轴平行，使得这个矩形的所有整数点的sum_x + sum_y，矩形可退化为一条线段或一个点
2方法：线段数学式子转化＋等差数列前n项和（内在规律）
3反思：
1>数据输出结果保证不会超过10e18，自己一开始用int型，Wrong Answer，之后比赛快结束了，匆忙改为long long unsigned型，然后for循环结束条件变成一个long long unsigned变量大于等于0，减1后回到long long unsigned变量可储存的最大值，然后for循环一直无限循环…

codeforces题目链接

以下为Time Limit Exceeded代码——未注意for循环结束条件为long long unsigned型变量大于等于零

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long unsigned y, x, m, b;
    long long unsigned ans, sum;
    while(~scanf("%llu %llu", &m, &b)){
        ans = 0;
        for(y = b; y >= 0; y--){
            x = b*m - m*y;
            sum = x*(x+1)*(y+1)/2 + y*(y+1)*(x+1)/2;
            ans = max(ans, sum);
        }
        printf("%llu\n", ans);
    }
    return 0;
}

以下为Accepted代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long x, y, m, b, sum, ans;
    while(~scanf("%lld %lld", &m, &b)){
        ans = 0;
        for(y = b; y >= 0; y--){
            x = b*m - y*m;
            sum = x*(x+1)*(y+1)/2 + y*(y+1)*(x+1)/2;
            ans = max(ans, sum);
        }
        printf("%lld\n", ans);
    }
    return 0;
}