【題意】
國王G最近決定重新設計一下皇陵。這個陵園必須包括兩個部分:每個墳墓必須是正方形的;必須由不同數量的墳墓組成。國王G在和他的占星家們讨論一番,他決定墳墓的邊長必須是連續正整數的序列。一條邊長為 s 包含s2個墳墓。國王G想要估計現在陵園中所有盡可能滿足設計條件的墳墓總數。你能幫他找到吧。
限制條件:
1≤n≤1014
【提煉】
求k組滿足條件的 a0…ar−1 (每組 r 個數),其平方之和等于輸入的正整數n。
【分析】
求連續平方數之和等于給定的數 n ,dp或者尺取法。
題目要求存下滿足條件的多組序列。
由于要提前輸出組數和每組的長度,是以采用vector + pair來存數組。右戳連結
Tips:判讀退出條件注意暫存一個值來判斷,不然wa到你懷疑人生。
【時間複雜度】
根據完全平方數的性質,正整數n以内的完全平方數數量總數為n√,是以立即推:
O(n√)
【代碼】
/*
coder: Tangent Chang
date: 2017/5/11
A day is a miniature of eternity. by Emerson
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const int maxn = ;
vector< pair<ll, ll> > ans;
int main() {
ll n;
while (scanf("%lld", &n) != EOF) {
ans.clear();
ll kk = ;
ll s = , t = , sum = , sq = ;
if (n == ) break;
while () {
while (sum < n) {
sq = t * t;
sum += sq;
t++;
}
if (sq > n) break;
if (sum == n) {
ans.push_back(make_pair(s, t));
}
sum -= s * s;
s++;
}
kk = ans.size();
printf("%lld\n", kk);
for (ll i = ; i < kk; ++i) {
ll l = ans[i].first;
ll r = ans[i].second;
printf("%lld", r - l);
for (ll j = l; j < r; ++j) {
printf(" %lld", j);
}
puts("");
}
}
return ;
}