結果
問題 | No.2392 二平方和 |
ユーザー |
|
提出日時 | 2023-07-28 22:06:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 33,980 bytes |
コンパイル時間 | 3,199 ms |
コンパイル使用メモリ | 222,384 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-06 18:58:46 |
合計ジャッジ時間 | 4,184 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define ALL(a) (a).begin(),(a.end())#define brep(n,hhh) for(int i=n-1;i>=hhh;i--)#define rep(hhh,n) for(int i=hhh;i<n;i++)#define jrep(hhh,n) for(int j=hhh;j<n;j++)#define krep(hhh,n) for(int k=hhh;k<n;k++)#define lrep(hhh,n) for(int l=hhh;l<n;l++)#define rrep(i,k,n) for(int i=k;i<n;i++)#define out(n) cout << n <<endl;#define sot(A) sort(A.begin(),A.end())#define rsot(A) sort(A.rbegin(),A.rend())#define vi vector<int>#define vb vector<bool>#define vd vector<double>#define vld vector<long double>#define vpd vector<pair<double,double>>#define vc vector<char>#define vs vector<string>#define vpi vector<pair<int,int>>#define vvc vector<vector<char>>#define vvi vector<vector<int>>#define vvd vector<vector<double>>#define vvpd vector<vector<pair<double,double>>>#define vvb vector<vector<bool>>#define vvvi vector<vector<vector<int>>>#define vvvvi vector<vector<vector<vector<int>>>>#define vvvpi vector<vector<vector<Pi>>>#define vvpi vector<vector<pair<int,int>>>#define vvtpi vector<vector<tuple<int,int,int>>>#define dout(x,y) cout<<x<<" "<<y<<endl;#define tout(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl;#define Pi pair<int,int>#define Pd pair<double,double>#define Pdi pair<double,int>#define TPi tuple<int,int,int>#define QPi tuple<int,int,int,int>#define FPi tuple<int,int,int,int,int>#define TPd tuple<double,int,int>#define spi pair<string,int>#define pb push_backconstexpr int MOD1=1000000007;constexpr int MOD2=998244353;constexpr int BIG=10000000000000000;//int BBB=ppow(2,31)-1;class BIT {public://データの長さint n;//データの格納先vector<int> a;//コンストラクタBIT(int n):n(n),a(n+1,0){}//a[i]にxを加算するvoid add(int i,int x){i++;if(i==0) return;for(int k=i;k<=n;k+=(k & -k)){a[k]+=x;//a[k]%=MOD2;}}void conf(){for(int i=0;i<=n;i++){cout<<a[i]<<' ';}cout<<endl;}//a[i]+a[i+1]+…+a[j]を求めるint sum(int i,int j){return (sum(j)-sum(i-1));}//a[0]+a[1]+…+a[i]を求めるint sum(int i){i++;int s=0;if(i==0) return s;for(int k=i;k>0;k-=(k & -k)){s+=a[k];//s%=MOD2;}return s;}//a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要)int lower_bound(int x){if(x<=0){//xが0以下の場合は該当するものなし→0を返すreturn 0;}else{int i=0;int r=1;//最大としてありうる区間の長さを取得する//n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求めるwhile(r<n) r=r<<1;//区間の長さは調べるごとに半分になるfor(int len=r;len>0;len=len>>1) {//その区間を採用する場合if(i+len<n && a[i+len]<x){x-=a[i+len];i+=len;}}return i;}}};class CR{public:vi fac;vi finv;vi inv;//int MOD;CR(int N):fac(N+1),finv(N+1),inv(N+1){//MOD=M;fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i <= N; i++){fac[i] = fac[i - 1] * i % MOD2;inv[i] = MOD2 - inv[MOD2%i] * (MOD2 / i) % MOD2;finv[i] = finv[i - 1] * inv[i] % MOD2;}}// 二項係数計算long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD2) % MOD2;}};//MODには素数namespace internal {template <class T> struct simple_queue {std::vector<T> payload;int pos = 0;void reserve(int n) { payload.reserve(n); }int size() const { return (int)(payload.size()) - pos; }bool empty() const { return pos == (int)(payload.size()); }void push(const T& t) { payload.push_back(t); }T& front() { return payload[pos]; }void clear() {payload.clear();pos = 0;}void pop() { pos++; }};}template <class Cap> struct mf_graph {public:mf_graph() : _n(0) {}mf_graph(int n) : _n(n), g(n) {}int add_edge(int from, int to, Cap cap) {assert(0 <= from && from < _n);assert(0 <= to && to < _n);assert(0 <= cap);int m = (int)(pos.size());pos.push_back({from, (int)(g[from].size())});int from_id = (int)(g[from].size());int to_id = (int)(g[to].size());if (from == to) to_id++;g[from].push_back(_edge{to, to_id, cap});g[to].push_back(_edge{from, from_id, 0});return m;}struct edge {int from, to;Cap cap, flow;};edge get_edge(int i) {int m = (int)(pos.size());assert(0 <= i && i < m);auto _e = g[pos[i].first][pos[i].second];auto _re = g[_e.to][_e.rev];return edge{pos[i].first, _e.to, _e.cap + _re.cap, _re.cap};}std::vector<edge> edges() {int m = (int)(pos.size());std::vector<edge> result;for (int i = 0; i < m; i++) {result.push_back(get_edge(i));}return result;}void change_edge(int i, Cap new_cap, Cap new_flow) {int m = (int)(pos.size());assert(0 <= i && i < m);assert(0 <= new_flow && new_flow <= new_cap);auto& _e = g[pos[i].first][pos[i].second];auto& _re = g[_e.to][_e.rev];_e.cap = new_cap - new_flow;_re.cap = new_flow;}Cap flow(int s, int t) {return flow(s, t, std::numeric_limits<Cap>::max());}Cap flow(int s, int t, Cap flow_limit) {assert(0 <= s && s < _n);assert(0 <= t && t < _n);assert(s != t);std::vector<int> level(_n), iter(_n);internal::simple_queue<int> que;auto bfs = [&]() {std::fill(level.begin(), level.end(), -1);level[s] = 0;que.clear();que.push(s);while (!que.empty()) {int v = que.front();que.pop();for (auto e : g[v]) {if (e.cap == 0 || level[e.to] >= 0) continue;level[e.to] = level[v] + 1;if (e.to == t) return;que.push(e.to);}}};auto dfs = [&](auto self, int v, Cap up) {if (v == s) return up;Cap res = 0;int level_v = level[v];for (int& i = iter[v]; i < (int)(g[v].size()); i++) {_edge& e = g[v][i];if (level_v <= level[e.to] || g[e.to][e.rev].cap == 0) continue;Cap d =self(self, e.to, std::min(up - res, g[e.to][e.rev].cap));if (d <= 0) continue;g[v][i].cap += d;g[e.to][e.rev].cap -= d;res += d;if (res == up) break;}return res;};Cap flow = 0;while (flow < flow_limit) {bfs();if (level[t] == -1) break;std::fill(iter.begin(), iter.end(), 0);while (flow < flow_limit) {Cap f = dfs(dfs, t, flow_limit - flow);if (!f) break;flow += f;}}return flow;}std::vector<bool> min_cut(int s) {std::vector<bool> visited(_n);internal::simple_queue<int> que;que.push(s);while (!que.empty()) {int p = que.front();que.pop();visited[p] = true;for (auto e : g[p]) {if (e.cap && !visited[e.to]) {visited[e.to] = true;que.push(e.to);}}}return visited;}private:int _n;struct _edge {int to, rev;Cap cap;};std::vector<std::pair<int, int>> pos;std::vector<std::vector<_edge>> g;};int ceil_pow2(int n) {int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()>struct lazy_segtree {public:lazy_segtree() : lazy_segtree(0) {}lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}lazy_segtree(const std::vector<S>& v) : _n((int)v.size()) {log = ceil_pow2(_n);size = 1 << log;d = std::vector<S>(2 * size, e());lz = std::vector<F>(size, id());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update(i);}}void set(int p, S x) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);return d[p];}S prod(int l, int r) {assert(0 <= l && l <= r && r <= _n);if (l == r) return e();l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push(r >> i);}S sml = e(), smr = e();while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_prod() { return d[1]; }void apply(int p, F f) {assert(0 <= p && p < _n);p += size;for (int i = log; i >= 1; i--) push(p >> i);d[p] = mapping(f, d[p]);for (int i = 1; i <= log; i++) update(p >> i);}void apply(int l, int r, F f) {assert(0 <= l && l <= r && r <= _n);if (l == r) return;l += size;r += size;for (int i = log; i >= 1; i--) {if (((l >> i) << i) != l) push(l >> i);if (((r >> i) << i) != r) push((r - 1) >> i);}{int l2 = l, r2 = r;while (l < r) {if (l & 1) all_apply(l++, f);if (r & 1) all_apply(--r, f);l >>= 1;r >>= 1;}l = l2;r = r2;}for (int i = 1; i <= log; i++) {if (((l >> i) << i) != l) update(l >> i);if (((r >> i) << i) != r) update((r - 1) >> i);}}template <bool (*g)(S)> int max_right(int l) {return max_right(l, [](S x) { return g(x); });}template <class G> int max_right(int l, G g) {assert(0 <= l && l <= _n);assert(g(e()));if (l == _n) return _n;l += size;for (int i = log; i >= 1; i--) push(l >> i);S sm = e();do {while (l % 2 == 0) l >>= 1;if (!g(op(sm, d[l]))) {while (l < size) {push(l);l = (2 * l);if (g(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*g)(S)> int min_left(int r) {return min_left(r, [](S x) { return g(x); });}template <class G> int min_left(int r, G g) {assert(0 <= r && r <= _n);assert(g(e()));if (r == 0) return 0;r += size;for (int i = log; i >= 1; i--) push((r - 1) >> i);S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!g(op(d[r], sm))) {while (r < size) {push(r);r = (2 * r + 1);if (g(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;std::vector<F> lz;void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }void all_apply(int k, F f) {d[k] = mapping(f, d[k]);if (k < size) lz[k] = composition(f, lz[k]);}void push(int k) {all_apply(2 * k, lz[k]);all_apply(2 * k + 1, lz[k]);lz[k] = id();}};namespace internal {template <class E> struct csr {std::vector<int> start;std::vector<E> elist;csr(int n, const std::vector<std::pair<int, E>>& edges): start(n + 1), elist(edges.size()) {for (auto e : edges) {start[e.first + 1]++;}for (int i = 1; i <= n; i++) {start[i] += start[i - 1];}auto counter = start;for (auto e : edges) {elist[counter[e.first]++] = e.second;}}};struct scc_graph {public:scc_graph(int n) : _n(n) {}int num_vertices() { return _n; }void add_edge(int from, int to) { edges.push_back({from, {to}}); }// @return pair of (# of scc, scc id)std::pair<int, std::vector<int>> scc_ids() {auto g = csr<edge>(_n, edges);int now_ord = 0, group_num = 0;std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);visited.reserve(_n);auto dfs = [&](auto self, int v) -> void {low[v] = ord[v] = now_ord++;visited.push_back(v);for (int i = g.start[v]; i < g.start[v + 1]; i++) {auto to = g.elist[i].to;if (ord[to] == -1) {self(self, to);low[v] = std::min(low[v], low[to]);} else {low[v] = std::min(low[v], ord[to]);}}if (low[v] == ord[v]) {while (true) {int u = visited.back();visited.pop_back();ord[u] = _n;ids[u] = group_num;if (u == v) break;}group_num++;}};for (int i = 0; i < _n; i++) {if (ord[i] == -1) dfs(dfs, i);}for (auto& x : ids) {x = group_num - 1 - x;}return {group_num, ids};}std::vector<std::vector<int>> scc() {auto ids = scc_ids();int group_num = ids.first;std::vector<int> counts(group_num);for (auto x : ids.second) counts[x]++;std::vector<std::vector<int>> groups(ids.first);for (int i = 0; i < group_num; i++) {groups[i].reserve(counts[i]);}for (int i = 0; i < _n; i++) {groups[ids.second[i]].push_back(i);}return groups;}private:int _n;struct edge {int to;};std::vector<std::pair<int, edge>> edges;};}struct scc_graph {public:scc_graph() : internal(0) {}scc_graph(int n) : internal(n) {}void add_edge(int from, int to) {int n = internal.num_vertices();assert(0 <= from && from < n);assert(0 <= to && to < n);internal.add_edge(from, to);}std::vector<std::vector<int>> scc() { return internal.scc(); }private:internal::scc_graph internal;};void conf(vs &A){for(string i:A){cout<<i<<' ';}cout<<endl;}void conf(vd &A){for(double i:A){cout<<i<<' ';}cout<<endl;}void conf(vi &A){for(int i:A){cout<<i<<' ';}cout<<endl;}void conf(vvvi &A,int k){rep(0,A.size()){jrep(0,A[i].size()){cout<<A[i][j][k]<<' ';}cout<<endl;}}void conf(set<int> &S){for(int i:S)cout<<i<<' ';cout<<endl;}void conf(vc &A){for(char i:A){cout<<i;}cout<<endl;}void conf(vvi &A){rep(0,A.size()){jrep(0,A[i].size()){cout<<A[i][j]<<" ";}cout<<endl;}}void conf(vvc &A){rep(0,A.size()){jrep(0,A[i].size()){cout<<A[i][j];}cout<<endl;}}void conf(vvb &A){rep(0,A.size()){jrep(0,A[i].size()){cout<<(int)A[i][j]<<" ";}cout<<endl;}}void conf(vvpi &A){rep(0,A.size()){jrep(0,A[i].size()){cout<<"("<<A[i][j].first<<" "<<A[i][j].second<<")"<<" ";}cout<<endl;}}void conf(vpi &A){rep(0,A.size()){cout <<'('<< A[i].first <<" "<<A[i].second<<')'<<" ";}cout<<endl;}int max(int a,int b){if(a>b)return a;else return b;}int min(int a,int b){if(a>b)return b;else return a;}int modpow(int x,int n,int mod){int res=1;while(n>0){int l=x%mod;if(n&1)res=(res%mod)*l%mod;x=l*l%mod;n>>=1;}return res;}//高速べき乗(modの値を返す)、計算量log(N)int ppow(int x,int n){int res=1;while(n>0){if(n&1)res=res*x;x=x*x;n>>=1;}return res;}//高速べき乗、計算量log(N)int modinv(int a, int m) {int b = m, u = 1, v = 0;while (b) {int t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}//拡張EuClidの互除法、逆元を返す,a,mが互いに素ならOK、mがMOD,log(a);vi smallest_prime_factors(int n) {vi spf(n + 1);for (int i = 0; i <= n; i++) spf[i] = i;for (int i = 2; i * i <= n; i++) {if (spf[i] == i) {for (int j = i * i; j <= n; j += i) {if (spf[j] == j) {spf[j] = i;}}}}return spf;}vector<int> enumdiv(int n) {vector<int> S;for (int i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }sort(S.begin(), S.end());return S;}//与えられた1つの数の約数をvectorで昇順で返す(重複なし),計算量√Nvi soinsu(int N){vi T;int n=N;int k=2;while(k*k<=n){if(N%k==0){N=N/k;T.push_back(k);}else{k++;}}if(N!=1)T.push_back(N);if(T.size()==0){T.push_back(n);}return T;}//素因数分解した結果をviで返す(sort済み),O(√N)int legendre(int N,int k){int ans=0;int K=k;while(N>=K){ans+=N/K;K*=k;}return ans;}//N!がkで何回割ることが出来るかvb Eratosthenes(int N){vb IsPrime(N+1,true);IsPrime[0] = false; // 0は素数ではないIsPrime[1] = false; // 1は素数ではないfor(int i=2; i*i<=N; ++i) // 0からsqrt(max)まで調べるif(IsPrime[i]) // iが素数ならばfor(int j=2; i*j<=N; ++j) // (max以下の)iの倍数はIsPrime[i*j] = false;return IsPrime;}//Nまでの数が素数か素数でないかを返す、計算量nloglognint lgcd(int A, int B){//int a,b,C;while (A!=0 && B!=0){if (A>B){//a=A/B;A-=A/B*B;}else{//b=B/A;B-=B/A*A;}//out(7)}//C=max(A,B);return max(A,B);}int lcm(int a, int b) {return a / lgcd(a, b) * b;}void YN(bool A){if(A){out("Yes");}else{out("No");}}double max(double a,double b){if(a>b){return a;}else{return b;}}double min(double a,double b){if(a>b){return b;}else{return a;}}vvi mat_mul(vvi &a, vvi &b,int MOD) {vvi res(a.size(), vi(b[0].size(),0));for (int i = 0; i < a.size(); i++) {for (int j = 0; j < b[0].size(); j++) {for (int k = 0; k < b.size(); k++) {(res[i][j] ^= a[i][k]&b[k][j]);}}}return res;}vvi mat_pow(vvi a, int n,int MOD) {int d=1;vvi res(a.size(), vi(a.size()));// 単位行列で初期化for (int i = 0; i < a.size(); i++)res[i][i] = (d<<33)-1;// 繰り返し二乗法while (n > 0) {if (n & 1) res = mat_mul(a, res,MOD);a = mat_mul(a, a,MOD);n >>= 1;}return res;}template <class S, S (*op)(S, S), S (*e)()> struct segtree {public:segtree() : segtree(0) {}segtree(int n) : segtree(std::vector<S>(n, e())) {}segtree(const std::vector<S>& v) : _n((v.size())) {log = ceil_pow2(_n);size = 1 << log;d = std::vector<S>(2 * size, e());for (int i = 0; i < _n; i++) d[size + i] = v[i];for (int i = size - 1; i >= 1; i--) {update(i);}}void set(int p, S x) {assert(0 <= p && p < _n);p += size;d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) {assert(0 <= p && p < _n);return d[p + size];}S prod(int l, int r) {assert(0 <= l && l <= r && r <= _n);S sml = e(), smr = e();l += size;r += size;while (l < r) {if (l & 1) sml = op(sml, d[l++]);if (r & 1) smr = op(d[--r], smr);l >>= 1;r >>= 1;}return op(sml, smr);}S all_prod() { return d[1]; }template <bool (*f)(S)> int max_right(int l) {return max_right(l, [](S x) { return f(x); });}template <class F> int max_right(int l, F f) {assert(0 <= l && l <= _n);assert(f(e()));if (l == _n) return _n;l += size;S sm = e();do {while (l % 2 == 0) l >>= 1;if (!f(op(sm, d[l]))) {while (l < size) {l = (2 * l);if (f(op(sm, d[l]))) {sm = op(sm, d[l]);l++;}}return l - size;}sm = op(sm, d[l]);l++;} while ((l & -l) != l);return _n;}template <bool (*f)(S)> int min_left(int r) {return min_left(r, [](S x) { return f(x); });}template <class F> int min_left(int r, F f) {assert(0 <= r && r <= _n);assert(f(e()));if (r == 0) return 0;r += size;S sm = e();do {r--;while (r > 1 && (r % 2)) r >>= 1;if (!f(op(d[r], sm))) {while (r < size) {r = (2 * r + 1);if (f(op(d[r], sm))) {sm = op(d[r], sm);r--;}}return r + 1 - size;}sm = op(d[r], sm);} while ((r & -r) != r);return 0;}private:int _n, size, log;std::vector<S> d;void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }};struct dsu {public:dsu() : _n(0) {}dsu(int n) : _n(n), parent_or_size(n, -1) {}int merge(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);int x = leader(a), y = leader(b);if (x == y) return x;if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);parent_or_size[x] += parent_or_size[y];parent_or_size[y] = x;return x;}bool same(int a, int b) {assert(0 <= a && a < _n);assert(0 <= b && b < _n);return leader(a) == leader(b);}int leader(int a) {assert(0 <= a && a < _n);if (parent_or_size[a] < 0) return a;return parent_or_size[a] = leader(parent_or_size[a]);}int size(int a) {assert(0 <= a && a < _n);return -parent_or_size[leader(a)];}std::vector<std::vector<int>> groups() {std::vector<int> leader_buf(_n), group_size(_n);for (int i = 0; i < _n; i++) {leader_buf[i] = leader(i);group_size[leader_buf[i]]++;}std::vector<std::vector<int>> result(_n);for (int i = 0; i < _n; i++) {result[i].reserve(group_size[i]);}for (int i = 0; i < _n; i++) {result[leader_buf[i]].push_back(i);}result.erase(std::remove_if(result.begin(), result.end(),[&](const std::vector<int>& v) { return v.empty(); }),result.end());return result;}private:int _n;// root node: -1 * component size// otherwise: parentstd::vector<int> parent_or_size;};vi topological_sort(vvi &G, vector<int> &indegree, int V) {// トポロジカルソートを記録する配列vector<int> sorted_vertices;// 入次数が0の頂点を発見したら、処理待ち頂点としてキューに追加するqueue<int> que;for (int i = 0; i < V; i++) {if (indegree[i] == 0) {que.push(i);}}// キューが空になるまで、操作1~3を繰り返すwhile (que.empty() == false) {// キューの先頭の頂点を取り出すint v = que.front();que.pop();// その頂点と隣接している頂点の入次数を減らし、0になればキューに追加for (int i = 0; i < G[v].size(); i++) {int u = G[v][i];indegree[u] -= 1;if (indegree[u] == 0) que.push(u);}// 頂点vを配列の末尾に追加するsorted_vertices.push_back(v);}// トポロジカルソートを返すreturn sorted_vertices;}vi dikstra(int s,int V,vvpi &G){vi d(V,BIG);priority_queue<Pi,vector<Pi>,greater<Pi>> que;d[s]=0;que.push(Pi(0,s));//Pi(距離、向かう頂点)while(!que.empty()){Pi p=que.top();que.pop();int v=p.second;if(d[v]<p.first)continue;rep(0,G[v].size()){int a=G[v][i].second;int b=G[v][i].first;if(d[a]>d[v]+b){d[a]=d[v]+b;que.push(Pi(d[a],a));}}}return d;}//始点は0start/*int op(int a, int b) {return max(a,b);}int e() {return 0;}*///int target;//bool f(int v) { return v >= target; }struct loopdfs{public:int flgggg;bool gg;bool x;int start;loopdfs(int n){flgggg=-1;gg=false;x=false;start=n;//0-indexed};void loops(int a,vvi &G,vb &seen,vi &loop,vi &prev){seen[a]=true;for (auto nv : G[a]) {if(gg)continue;if (seen[nv]){flgggg=nv;gg=true;x=true;break;}loops(nv,G,seen,loop,prev);}if(!gg&&x){prev.push_back(a);}if(gg){loop.push_back(a);}if(flgggg==a)gg=false;if(a==start){reverse(loop.begin(),loop.end());reverse(prev.begin(),prev.end());}}//有向なfunctional graphのみ動作確認、};vvi calcNext(const string &S) {int n = (int)S.size();vector<vector<int> > res(n+1, vector<int>(26, n));for (int i = n-1; i >= 0; --i) {for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];res[i][S[i]-'a'] = i;}return res;}struct S{int v;//int size;};S op(S a,S b){return {min(a.v,b.v)};}S e(){return {BIG};}S mapping(int a, S b){return {a+b.v};}int composition(int a,int b){return a+b;}int id(){return 0;}vi compress(vi &A){vi vals=A;sot(vals);vals.erase(unique(vals.begin(), vals.end()), vals.end());vi X(A.size());rep(0,A.size()){X[i]=lower_bound(vals.begin(),vals.end(),A[i])-vals.begin();}return X;}//0-indexedtemplate <typename T>vector<T> compress(vector<T> &C1, vector<T> &C2,int w) {vector<T> vals;int N = (int)C1.size();for (int i = 0; i < N; i++) {for (int d = 0; d <= 0; d++) { // for (T d = 0; d <= 0; d++) でも良いT tc1 = C1[i] - d;if(tc1>=0){vals.push_back(tc1);}T tc2 = C2[i] + d;if(tc2<=w){vals.push_back(tc2);}}}sort(vals.begin(), vals.end());vals.erase(unique(vals.begin(), vals.end()), vals.end());for (int i = 0; i < N; i++) {C1[i] = lower_bound(vals.begin(), vals.end(), C1[i]) - vals.begin();C2[i] = lower_bound(vals.begin(), vals.end(), C2[i]) - vals.begin();}return vals;}//2次元座標圧縮int kruskal(vector<TPi> &A,int V){sot(A);int M=A.size();dsu uf(V+1);int res=0;rep(0,M){int a=get<1>(A[i]);int b=get<2>(A[i]); int c=get<0>(A[i]);if(!uf.same(a,b)){uf.merge(a,b);res+=c;}}bool flag=false;rep(1,V+1){if(!uf.same(i,0))flag=true;}if(flag){res=-1;}return res;}string encode(string& str) {string ret = ""; // 答えを格納int n=(int)(str.size());for (int l = 0; l < n;) {int r = l + 1;while(r < n && str[l] == str[r]){r++;}ret.push_back(str[l]);char num_str = (char)((r - l)+'0'); // 出現回数ret += num_str;l = r;}return ret;}bool revsort(const Pi &a,const Pi &b){if(a.first>b.first){return true;}else{if(a.first==b.first){if(a.second<b.second){return true;}else{return false;}}else{return false;}}}//Piでfirst降順、second昇順bool anglesortbool(const Pi &a,const Pi &b){int x=a.first*b.second-a.second*b.first;if(x>0){return true;}else{return false;}}vpi anglesort(vpi &A){vvpi qua(4);rep(0,A.size()){int x=A[i].first;int y=A[i].second;if(x>0&&y>=0){qua[0].push_back(Pi(x,y));}if(x<=0&&y>0){qua[1].push_back(Pi(x,y));}if(x<0&&y<=0){qua[2].push_back(Pi(x,y));}if(x>=0&&y<0){qua[3].push_back(Pi(x,y));}}rep(0,4){sort(qua[i].begin(),qua[i].end(),anglesortbool);}vpi B;rep(0,4){jrep(0,qua[i].size()){B.pb(qua[i][j]);}}return B;}//偏角ソート、pairの値は10^9まで、0から2Πを昇順にソートvoid dfs1(vvb &G,int h,int w,int H,int W){if(G[h][w])return;G[h][w]=true;vi dh={1,0,-1,0};vi dw={0,1,0,-1};rep(0,4){int x=h+dh[i];int y=w+dw[i];if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(!G[x][y])){//out(9);dfs1(G,x,y,H,W); // 再帰的に探索}}//A[h][w]=1;}void dfs(vb &seen,int a,vvi &G){if(seen[a])return;seen[a]=true;for(int i:G[a]){if(seen[i])continue;//seen[i]=true;dfs(seen,i,G); // 再帰的に探索}//A[h][w]=1;}template< typename T >struct SparseTable {vector< vector< T > > st;vector< int > lookup;SparseTable(const vector< T > &v) {int b = 0;while((1 << b) <= v.size()) ++b;//out(b)st.assign(b, vector< T >(1 << b));for(int i = 0; i < v.size(); i++) {st[0][i] = v[i];}//conf(st);for(int i = 1; i < b; i++) {for(int j = 0; j + (1 << i) <= (1 << b); j++) {st[i][j] = lgcd(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);//変更する}}lookup.resize(v.size() + 1);for(int i = 2; i < lookup.size(); i++) {lookup[i] = lookup[i >> 1] + 1;}}inline T gcd(int l, int r) {//conf(st);if(l==r){return 0;//変更する}int b = lookup[r - l];//out(st[b][r - (1 << b)])return lgcd(st[b][l], st[b][r - (1 << b)]);}//変更する};int bdp2(int N,int bit,vi &dp,vb &seen){if(seen[bit]){//out(7)return dp[bit];}//out(7)int res = dp[bit];brep((1<<N),0){i&=bit;int pbit=bit&(~i);if(i==0||pbit==0)continue;//dout(bit,pbit)res=min(bdp2(N,i,dp,seen)+bdp2(N,pbit,dp,seen),res);}seen[bit]=true;return dp[bit]=res; // メモしながらリターン}vvi bfs3(vvc &G,vvi &A,int h,int w,int H,int W){vi dh={1,0,-1,0};vi dw={0,1,0,-1};A[h][w]=0;queue<Pi> que;que.push(Pi(h,w));while(!que.empty()){Pi v=que.front();que.pop();rep(0,4){int x=v.first+dh[i];int y=v.second+dw[i];if(x>=0&&x<=H-1&&y>=0&&y<=W-1&&(A[x][y]==-1)&&G[x][y]!='#'){que.push(Pi(x,y));A[x][y]=A[v.first][v.second]+1;}}}return A;}signed main(){int P;cin>>P;bool flag=false;int k=1;while(k*k<=P){int x=sqrt(P-k*k);if(k*k+x*x==P)flag=true;k++;}YN(flag);}