結果

問題 No.2479 Sum of Squares
ユーザー AerenAeren
提出日時 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 #
プレゼンテーションモードにする

#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 //
// //
////////////////////////////////////////////////////////////////////////////////////////
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0