Codeforces 599D Spongebob and Squares【思维枚举+数学方程】

Spongebob is already tired trying to reason his weird actions and calculations, so he simply asked you to find all pairs of n and m, such that there are exactlyx distinct squares in the table consisting ofn rows and m columns. For example, in a3 × 5 table there are 15 squares with side one,8 squares with side two and 3 squares with side three. The total number of distinct squares in a 3 × 5 table is 15 + 8 + 3 = 26.

Input

The first line of the input contains a single integer x (1 ≤ x ≤ 10¹⁸) — the number of squares inside the tables Spongebob is interested in.

Output

First print a single integer k — the number of tables with exactlyx distinct squares inside.

Then print k pairs of integers describing the tables. Print the pairs in the order of increasingn, and in case of equality — in the order of increasingm.

ExamplesInput

Output

Input

Output

2
1 2
2 1

Input

Output

Note

In a 1 × 2 table there are 2 1 × 1 squares. So, 2 distinct squares in total.

$Codeforces 599D Spongebob and Squares【思维枚举+数学方程】$

In a 2 × 3 table there are 6 1 × 1 squares and 22 × 2 squares. That is equal to 8 squares in total.

$Codeforces 599D Spongebob and Squares【思维枚举+数学方程】$

题目大意：

让你求一共有多少种方案，使得n*m的正方形中，有k个子正方形。

思路：

1、首先很明显，对于一个3*5的正方形中，其有子正方形：n*m+（n-1）*（m-1）+（n-2）*（m-2）==26个；

那么同理，对于一个n*m的正方形中，其有子正方形：

tmp=min（n，m）；

数量=n*m*tmp-【（tmp）*（tmp-1）/2】*（x+y）+1^2+2^2+3^2+4^2+..........(tmp-1)^2；

那么问题就转化成为：有多少个x，使得n*m*tmp-【（tmp）*（tmp-1）/2】*（n+m）+1^2+2^2+3^2+4^2+..........(tmp-1)^2==X.

2、接下来观察等式，等式右侧一定是大于等于1的一个数，那么肯定一点，如果1^2+2^2+..........+(tmp-1)^2大于了X.那么显然就是无解的。

那么我们着重讨论1^2+2^2+.............+(tmp-1)^2.

打个暴力的表，并且存到sum【i】，表示1^2+2^2+.........+i^2的值。

当sum【i】>1e18的时候跳出，不难发现，这个数组的长度是1e6+的。

那么我们可以考虑枚举n，同时设定tmp==n，对于剩下已知部分，很容易就能求得m。

接下来的任务就变成了解方程式，求y.

对于求出的解进行统计即可。

3、注意n==m的时候，千万不能多输出。（被这里坑了一波，很蓝廋）；

Ac代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll __int64
struct node
{
    ll x,y;
}ans[1442275];
ll sum[1442275];
int tot;
int cmp(node a,node b)
{
    return a.x<b.x;
}
void init()
{
    ll summ=0;
    for(ll i=1;i<=100000000;i++)
    {
        summ+=i*i;
        if(summ>=1000000000000000000)
        {
            tot=i-1;
            break;
        }
        sum[i]=summ;
    }
}
int main()
{
    init();
    ll x;
    while(~scanf("%I64d",&x))
    {
        int cnt=0;
        for(ll i=1;i<=tot;i++)
        {
            if(x>=sum[i])
            {
                ll right=x-sum[i-1];
                right+=(i-1)*i*i/2;
                right*=2;
                if(right%(i*i+i)==0)
                {
                    ll y=right/(i*i+i);
                    ans[cnt].x=i;
                    ans[cnt++].y=y;
                    ans[cnt].x=y;
                    ans[cnt++].y=i;
                    if(i==y)cnt--;
                }
            }
        }
        sort(ans,ans+cnt,cmp);
        printf("%d\n",cnt);
        for(int i=0;i<cnt;i++)
        {
            printf("%I64d %I64d\n",ans[i].x,ans[i].y);
        }
    }
}

秒客网

Codeforces 599D Spongebob and Squares【思维枚举+数学方程】

相关文章