「マルチプル・テーブル」問題

codeiq_kukuhako.cc

#include<bits/stdc++.h>

using namespace std;
typedef long long int ll;

// (x1,y1) (x2,y2)で囲まれた長方形の領域の総和を求める
// inline ll rect(ll x1,ll y1,ll x2,ll y2){
//     return (y2*(y2+1)-(y1-1)*y1)*(x2*(x2+1)-(x1-1)*x1)/4;
// }

// rectの式をy1の関数にしたもの。(ただしx2=x1)
inline ll calc_y1(ll x1,ll y2,ll sum){
    ll t;
    if ((t=x1-8*sum+4*x1*y2*(y2+1))<=10*x1) return 1;
    return (0.5+sqrt(0.25*t/x1));
}

int main(){
    int x,y,px,py,h;
    int n,r;
    int result=0;
    
    cin>>n; // 3000000
    
    int sqn=sqrt(n);

    for (py=1;py<=sqn;py++){
        for (px=1;px*py<=n;px++){
            for (y=calc_y1(px,py,n);y<=py;y++){
                h=(py*(py+1)-y*(y-1))/2;
                r=0;
                for (x=px;y<=x;x--){
                    r+=h*x;
                    if (r>n) break;
                    if (r==n){
                        //printf("%d %d %d %d",x,y,px,py);cout<<endl;
                        result+= y!=x ? 2 : 1;
                        break;
                    }
                }
            }
        }
    }
    cout<<result<<endl;

    return 0;
}