結果

問題 No.2479 Sum of Squares
コンテスト
ユーザー tonegawa
提出日時 2023-09-23 02:33:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 6,966 bytes
コンパイル時間 1,217 ms
コンパイル使用メモリ 139,684 KB
最終ジャッジ日時 2025-02-17 01:16:38
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 1 ".lib/template.hpp"


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){
  dest << p.first << ' ' << p.second;
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz;i++){
    int m = v[i].size();
    for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');
  }
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){
  int sz = v.size();
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T, size_t sz>
std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){
  if(sz==0) return dest;
  for(int i=0;i<sz-1;i++) dest << v[i] << ' ';
  dest << v[sz-1];
  return dest;
}
template<typename T>
std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << *itr;
    itr++;
    if(itr!=v.end()) dest << ' ';
  }
  return dest;
}
template<typename T, typename E>
std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){
  for(auto itr=v.begin();itr!=v.end();){
    dest << '(' << itr->first << ", " << itr->second << ')';
    itr++;
    if(itr!=v.end()) dest << '\n';
  }
  return dest;
}
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
template<typename T>
vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}
template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail){
  return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}
template<typename T>
vector<T> read_vec(size_t sz){
  std::vector<T> v(sz);
  for(int i=0;i<(int)sz;i++) std::cin >> v[i];
  return v;
}
template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail){
  auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
  for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);
  return v;
}
void io_init(){
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
}

#line 2 "a.cpp"

/*
ll solve_small(int a, int b, int c, int d, int e, int f){

}
void solve(){
  int a, b, c, d, e, f;
  std::cin >> a >> b >> c >> d >> e >> f;
  // (1)     (2)     (3)    (4)
  // #       # #     # #      #
  // # #     #         #    # #
  
  // 1回で同じ位置の異なる形
  // 2回で上下左右に1個ずらした同型
  // 1回で
  // (2, 3, 4) -> 2回で右上に1個ずらした(1, 2, 4)
  // (1, 3, 4) -> 2回で右下に1個ずらした()
  // ...
}
*/

struct four_square_theorem{
  int n;
  std::vector<int> A;
  std::vector<int> sz;
  // 0 <= i < Nについて以下のテーブルを作る
  // sum(A) = iを満たしlen(A)が最小(常に4つ以下になる)
  // O(N√N)
  void init(int _n){
    n = _n;
    A.resize(n, -1);
    sz.resize(n, 5);
    sz[0] = 0;
    for(int i = 1; i < n; i++){
      for(int j = 1; j * j <= i; j++){
        if(sz[i - j * j] + 1 < sz[i]){
          A[i] = j;
          sz[i] = sz[i - j * j] + 1;
        }
      }
    }
  }
  four_square_theorem(int _n){
    init(_n);
  }
  // x = ∑A[i]^2 を満たす要素数最小のA(高々4つ)
  std::vector<int> get_square(int x){
    assert(n);
    assert(0 <= x && x < n);
    std::vector<int> ret;
    while(x){
      int y = A[x];
      ret.push_back(y);
      x -= y * y;
    }
    return ret;
  }
  // x = ∑A[i]^2 を満たすA(要素数最小とは限らない, N = 10^5, x < 10^18なら高々6要素になる)
  // @param x <= 10^18
  std::vector<unsigned long long> get_square_large(unsigned long long x){
    std::vector<unsigned long long> ret;
    while(n <= x){
      unsigned long long y = sqrtl(x);
      ret.push_back(y);
      x -= y * y;
    }
    while(x){
      int y = A[x];
      ret.push_back(y);
      x -= y * y;
    }
    return ret;
  }
  // x = ∑ A[i] * (A[i] + 1) / 2 を満たすA(3つ以下)
  std::vector<int> get_trianglar(int x){
    auto v = get_square(8 * x + 3);
    assert(v.size() == 3);
    std::vector<int> ret;
    for(int i = 0; i < 3; i++) if(v[i] != 1) ret.push_back(v[i] / 2);
    return ret;
  }
  // x = ∑ A[i] * (A[i] + 1) / 2 を満たすA(要素数最小とは限らない, N = 10^5, x < 10^18なら高々5要素になる)
  // @param x <= 10^18
  std::vector<unsigned long long> get_trianglar_large(unsigned long long x){
    std::vector<unsigned long long> ret;
    while(n <= 8 * x + 3){
      unsigned long long y = sqrtl(2 * x);
      while(y * (y + 1) > 2 * x) y--;
      ret.push_back(y);
      x -= (y & 1 ? y * ((y >> 1) + 1) : (y >> 1) * (y + 1));
    }
    auto v = get_square(8 * x + 3);
    for(int i = 0; i < 3; i++) if(v[i] != 1) ret.push_back(v[i] / 2);
    return ret;
  }
};

// ピタゴラス数について
// a^2 + b^2 = c^3を満たす自然数の組(a, b, c)をピタゴラス数と呼ぶ
// bが偶数, a, cが奇数でなければならない
// 自然数x, y(x > y)を用いて(a, b, c) = (x^2 - y^2, 2xy, x^2 + y^2)を表すことができる　

int main(){
  io_init();
  ll S;
  std::cin >> S;
  four_square_theorem f(100000);
  auto ans = f.get_square_large(S);
  range(i, 0, ans.size()) ans[i] *= ans[i];
  std::cout << ans.size() << '\n';
  std::cout << ans << '\n';
}
0