結果

問題 No.2479 Sum of Squares
コンテスト
ユーザー Aeren
提出日時 2023-09-22 21:23:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 1,882 bytes
コンパイル時間 3,520 ms
コンパイル使用メモリ 255,224 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-08 12:02:17
合計ジャッジ時間 3,485 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
using namespace numbers;

// Find floor(n^1/k) for non-negative integers n, k
struct floored_root{
	vector<unsigned long long> pow[65];
	floored_root(){
		for(auto t = 2u; t < 1 << 16; ++ t){
			unsigned long long s = t * t;
			s = s * s;
			for(auto k = 4; ; ++ k){
				pow[k].push_back(s);
				if(__builtin_umulll_overflow(s, t, &s)) break;
			}
		}
	}
	unsigned long long sqrt(unsigned long long n) const{
		if(n == -1ull) return (unsigned int)-1;
		unsigned long long x = std::sqrt(n);
		return x * x > n ? x - 1 : x;
	}
	unsigned long long cbrt(unsigned long long n) const{
		unsigned long long x = 0, y = 0;
		for(auto s = 63; s >= 0; s -= 3){
			x <<= 1;
			y = 3 * x * (x + 1) + 1;
			if(y <= (n >> s)) n -= y << s, ++ x;
		}
		return x;
	}
	unsigned long long operator()(unsigned long long n, int k) const{
		assert(1 <= k && k <= 64);
		if(k == 1 || n == 0) return n;
		if(k == 2) return sqrt(n);
		if(k == 3) return cbrt(n);
		return upper_bound(pow[k].begin(), pow[k].end(), n) - pow[k].begin() + 1;
	}
} F;

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	long long s;
	cin >> s;
	vector<long long> a;
	while(s){
		a.push_back(F.sqrt(s));
		a.back() *= a.back();
		s -= a.back();
	}
	cout << (int)a.size() << "\n";
	ranges::copy(a, ostream_iterator<long long>(cout, " "));
	cout << "\n";
	return 0;
}

/*

*/

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                                   Coded by Aeren                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////
0