推推乐

对于

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(x+1)(-x+1)}{3x(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;
}

题解：CF599D Spongebob and Squares

文章操作

推推乐

Code

相关推荐

评论

题解：CF599D Spongebob and Squares