poj2100(尺取法)

时间:2023-03-09 01:11:10
poj2100(尺取法)

题意:选取一系列数,使得这些数的平方和等于n;

解题思路:尺取法扫一遍;

#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int bin;
int len;
}a[];
int main()
{
long long right=,left=,cnt=;
long long sum=,n;
cin>>n;
while()
{
while(sum<n)
{
sum+=right*right;
right++;
}
if(sum==n)
{
cnt++;
a[cnt].bin=left;
a[cnt].len=right-left;
}
sum=sum-left*left;
left++;
if(left*left>n)
break;
}
cout<<cnt<<endl;
for(int i=;i<=cnt;i++)
{
cout<<a[i].len<<" ";
for(int j=;j<=a[i].len;j++)
{
cout<<a[i].bin++;
if(j<=a[i].len-)
cout<<" ";
}
cout<<endl;
}
return ;
}