http://codeforces.com/problemset/problem/599/D
题意:
给出一个数x,问你有多少个n*m的网格中有x个正方形,输出n和m的值。
思路:
易得公式为:$\sum_{i=0}^{n}(n-i)(m-i) $
化简得:$\left [ n(n+1)-\frac{n(n+1)}{2}\right ]*m+\frac{n(n+1)(n+2)}{6}-\frac{n(n+1)}{2}*n$
将n作为小的数,枚举n即可。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std; typedef long long ll;
typedef pair<ll,ll> pll; ll x;
vector<pll> ans1,ans2; int main()
{
//freopen("in.txt","r",stdin);
ll tot = ;
scanf("%lld",&x);
for(ll n=;;n++)
{
ll a = n*(n+) - n*(n+)/;
ll b = n*(n+)*(*n+)/ - n*n*(n+)/;
if(b > x) break;
if((x - b)%a == )
{
ll m = (x - b)/a;
if(m<n) continue;
ans1.push_back(make_pair(n,m));
tot++;
if(m!=n)
{
ans2.push_back(make_pair(m,n));
tot++;
}
}
}
printf("%lld\n",tot);
for(int i=;i<ans1.size();i++)
{
printf("%lld %lld\n",ans1[i].first,ans1[i].second);
}
for(int i=ans2.size()-;i>=;i--)
{
printf("%lld %lld\n",ans2[i].first,ans2[i].second);
}
return ;
}