codeforces 599D Spongebob and Squares

很容易得到n × m的方块数是

然后就是个求和的问题了，枚举两者中小的那个n ≤ m。

然后就是转化成a*m + c = x了。a,m≥0，x ≥ c。最坏是n^3 ≤ x，至于中间会不会爆，测下1e18就好。

#include<bits/stdc++.h>
using namespace std;

typedef long long ull;

vector<ull> ns;
vector<ull> ms;

//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    ull x, t, c, a, n, m; cin>>x;
    int k = 0;
    //ns.push_back(1); ms.push_back(x);
    int equ = 0;
    for(n = 1;  ; n++){
        t = n*(n+1)/2;
        c = (n)*(n+1)*(2*n+1)/6 - n*t;
        if(c > x) break;
        a = n*(n+1) - t;
        if((x - c) % a == 0) {
            m = (x-c)/a;
            if(m < n) break;
            ns.push_back(n);
            ms.push_back(m);
            k++;
            if(m == n){
                equ = 1; break;
            }
        }
    }

    if(equ){
        k = 2*k-1;
        printf("%d
", k);
        int sz = ns.size();
        for(int i = 0; i < sz; i++){
            printf("%I64d %I64d
", ns[i], ms[i]);
        }
        for(int i = sz-2; i >= 0; i--){
            printf("%I64d %I64d
", ms[i], ns[i]);
        }
    }
    else {
        k = 2*k;
        printf("%d
", k);
        int sz = ns.size();
         for(int i = 0; i < sz; i++){
            printf("%I64d %I64d
", ns[i], ms[i]);
        }
        for(int i = sz-1; i >= 0; i--){
            printf("%I64d %I64d
", ms[i], ns[i]);
        }
    }


    return 0;
}