题解：CF599D Spongebob and Squares
weisongze
·
·
题解
推推乐
对于 x \times y 的表格，显然如果 x \times y 成立，那么 y \times x 也成立，于是我们假设 x \leq y。
对于 i \times i 的正方形，方案数为 (x-i+1)(y-i+1)，所以总方案为 \sum\limits_{i=1}^{x}(x-i+1)(y-i+1)。
如果 i 表示能放下多少个正方形，那么上式也等价于 \sum\limits_{i=1}^{x}i\cdot(y-x+i)，两种表示都行（这种更好化简但难想一点）。
这个式子显然可以将求和化掉：\frac{x(x+1)(y-x)}{2}+\frac{x(x+1)(2x+1)}{6}
通分：\frac{x(x+1)(2x+1)+3x(x+1)(y-x)}{6}
合并：\frac{x(x+1)(3y-x+1)}{6}
化简到这里可以发现，两项最少要到 10^6，如果枚举 x 和 y 会爆，只能枚举 x，所以我们要变换这个式子将 y 表示出来。
设总方案为 t 实际上就是输入但我懒得改了。
t=\frac{x(x+1)(3y-x+1)}{6}
6t=x(x+1)(3y-x+1)
提出 y：
6t=3yx(x+1)+x(x+1)(-x+1)
移项：
3yx(x+1)=6t-x(x+1)(-x+1)
系数化一：
这里就可以算了，我再化简分子：$y=\frac{6t+x^3-x}{3x(x+1)}$。
于是我们终于推出……接下来枚举 $x$ 看是否存在整数的合法 $y$ 就行了。
# Code
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define F(i,x,y) for(i=x;i<=y;i++)
#define rF(i,x,y) for(i=x;i>=y;i--)
int x,y;
pair<int,int> ans[1000005];
signed main()
{
int i,sum=0,cnt=0;
cin>>x;
F(i,1,2000000)
{
if(i>x) break;
y=(6*x+i*i*i-i)/3/(i*i+i);
if((6*x+i*i*i-i)%(3*(i*i+i))!=0||y<i) continue;
ans[++cnt]={i,y},sum+=(i==y);
}
cout<<cnt*2-sum<<endl;
F(i,1,cnt) cout<<ans[i].first<<' '<<ans[i].second<<endl;
rF(i,cnt,1) if(ans[i].first!=ans[i].second)cout<<ans[i].second<<' '<<ans[i].first<<endl;
return 0;
}
```