結果
問題 | No.2479 Sum of Squares |
ユーザー |
|
提出日時 | 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 |
ソースコード
#include <bits/stdc++.h>// #include <x86intrin.h>using namespace std;using namespace numbers;// Find floor(n^1/k) for non-negative integers n, kstruct 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 //// //////////////////////////////////////////////////////////////////////////////////////////