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

51nod – 1659 – 数方块 – 简单数学https://www.51nod.com/Challenge/Problem.html!problemId=1659随便弄了一下发现公式,然后从cheatsheet抄一抄平方和公式,发现可以提公因式。提完发现可以放缩估计出n的上界,复杂度可行。然后是怎么求m。一开始弄了个假算法,要求每

大家好,欢迎来到IT知识分享网。51nod

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);
        }
    }
}

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/33874.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信