51nod - 1659 - 数方块

https://www.51nod.com/Challenge/Problem.html#!#problemId=1659

随便弄了一下发现公式，然后从cheatsheet抄一抄平方和公式，发现可以提公因式。

提完发现可以放缩估计出n的上界，复杂度可行。

然后是怎么求m。

一开始弄了个假算法，要求每一步都是整数，其实并不是这样。

经过一顿处理，又怕溢出ll这么麻烦。

最后分两步验证233。

保证结果是整数，那么参加加减法的都是整数，参加乘法的，把系数提到外面，然后保证里面是外面系数的倍数，这样刚好不会溢出。

然后顺手防一波n,m相等bug。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

int solve();

int main() {

#ifdef Yinku

    freopen("Yinku.in","r",stdin);

#endif // Yinku

    solve();

}

ll x;

vector<pair<ll,ll> >ans;

int solve() {

    while(~scanf("%lld",&x)) {

        ans.clear();

        for(ll n=1ll; n<=2000000ll; n++) {

            if((6ll*x)%(n*(n+1ll))) {

                continue;

            } else if(((6ll*x)/(n*(n+1ll))-(2ll*n+1ll))%3ll) {

                continue;

            } else {

                ll m=(6ll*x/(n*(n+1ll))-(2ll*n+1ll))/3ll+n;

                if(m>n) {

                    ans.push_back({n,m});

                    ans.push_back({m,n});

                } else if(m==n) {

                    ans.push_back({m,m});

                }

            }

        }

        sort(ans.begin(),ans.end());

        int n=(int)ans.size();

        printf("%d\n",n);

        for(int i=0; i<n; i++) {

            printf("%lld %lld\n",ans[i].first,ans[i].second);

        }

    }

}

巴特西

51nod - 1659 - 数方块 - 简单数学

最新文章

热门文章