# 题面

Anon作为海归高知，非常喜欢数学，有一天，她学到了费马平方和定理，该定理如下：

对于任意素数pp，存在两个正整数a和b，使得 $a^2$ + $b^2$ =p, 当且仅当p≡1(mod4)或p=2

Anon第二天和Soyo分享了这个定理，Soyo却反过来询问Anon："对于任意的数字n，什么时候可以被分解为两个正整数的平方和？"
Anon经过一夜的苦思冥想，并借助GPT的帮助，终于知道了什么时候n可以被分解平方和，次日Anon要面对Soyo的q次提问，每次询问一个数n，Anon只需要回答"Yes"或"No"表示该数是否可以被分解为平方和，而Anon觉得这个问题太简单了，就将这份任务交给你了。

正式描述如下：给出q个询问，第 $i$ 次给出一个正整数 $n_i$ ，你需要确定是否存在两个正整数a,b使得 $a^2$ + $b^2$ = $n_i$ ，输出"Yes"或"No"表示是否可以被分解为两个正整数的平方和。

请使用较快的输入输出方式。

例如：如果你使用的是cin/cout，请在main函数开头加入以下代码以加速输入输出：

ios::sync_with_stdio(nullptr); cin.tie(nullptr); cout.tie(nullptr);

# 输入格式

第一行包括一个正整数q(1≤q≤ $10^6$ )，表示询问的次数。
接下来的q行，第 $i$ 行包括一个正整数 $n_i$ (1≤ $n_i$ ≤2× $10^7$ )，表示第 $i$ 次询问的数。

# 输出格式

输出q行，第 $i$ 行输出Yes或No，表示 $n_i$ 是否能被分解为两个正整数的平方和

# 样例

输入数据1

10 1 2 3 4 5 6 7 8 9 10

输出数据1

No Yes No No Yes No No Yes No Yes

# 提示

对于样例，可以发现 $2$ = $1^2$ + $1^2$ ，5= $1^2$ + $2^2$ ， $8$ = $2^2$ + $2^2$ ， $10$ = $1^2$ + $3^2$ ，而其余剩余的都不能被分解为两个正整数的平方和。

注意，要求是分解成正整数的平方和，因此 $1$ 不能被分解为 $1^2$ + $0^2$

注：p≡1(mod4)表示p除4的余数为1

# 思路

事实上就是打表但是比赛的时候犯了至少两次傻导致没写出来

忘记了打表可以用一个数组来记录这个数存不存在想着再写一个程序把数全部跑出来填在if()里面唐死了
明明可以在但 $a^2$ + $b^2$ >= $2e7$ 的时候直接截断但是没想到想着把里外全部跑一遍 $3162^2$
OK下面正式思路
给了数据范围 $2e7$ 那么可以把打表的范围看作一个半径 $\sqrt{2e7}$ 的圆的 $\frac{1}{8}$ （结论）
所以数据量大概是 $$ 7,850,000 = \frac{3.14}{8} × 2e7 $$
众所周知计算机一秒运算次数大概是 $1e9$ 所以一般不会TLE
直接上代码吧

#include <bits/stdc++.h>
#define int long long 
const int MAX = 20000005 ;\\ 特有的开大一点防止莫名其妙的问题
using namespace std ;
int sum[MAX] ;
void graph(){
  for (int a = 1 ; a * a < MAX ; a++){
    for (int b = 1 ; ; b ++){
      int sm = a*a + b*b ;
      if (sm >= MAX) break ;
      sum[sm] = 1 ;
    }
  }
}
int ot(){
  int n ;
  cin >> n; 
  if (sum[n]) {
    cout << "Yes" <<'\n' ;
    return 0 ;
  }
  else {
    cout << "No" << '\n' ;
    return 0 ;
  }
}
signed main () {
  ios::sync_with_stdio(0) ;
  cin.tie(0) ;
  graph() ;
  int _ ;
  cin >> _ ;
  while (_--) {
    ot() ;
  }
}

ACM