Power Sum

2021 CCPC 网络预选赛 - F

---

题型分析

平方数性质+构造

题目描述&数据范围

题解

连续 $4$ 个平方数相加减可以得出固定值 $4$ ，即
$$
i^2-(i-1)^2=2i-1
$$

$$
(i-2)^2-(i-3)^2=2i-5
$$

两式相减得
$$
(i^2-(i-1)^2)-((i-2)^2-(i-3)^2)=4
$$
而整数 $1,2,3$ 能够通过 "1","0001","01" 最多四位字符串表示

因此对于整数 $n$ ，可以通过有最多 $n+2$ 个平方数相加减来构成

代码

#include <bits/stdc++.h>
#define sc static
using namespace std;
using ll=long long;
const int N=1e6+5;
string s[]={"1001","1","0001","01"};

void solve(){
	int n;cin>>n;
	int mod=n%4;
	int k=n/4;
	string ans="";
	if(mod)ans=s[mod];
	for(int i=1;i<=k;++i)ans+=s[0];
	cout<<ans.size()<<'\n';
	cout<<ans<<'\n';
}
int main(){
	/ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;
	cin>>t;
	while(t--) solve();
	return 0;
}