#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e6 + 10;
typedef long long ll;

int primes[N], cnt; 
bool st[N]; 

void get_primes(int n) // 线性筛
{   
    st[1] = true;//1不是质数
    for (int i = 2; i <= n; i ++ )//从2开始     从 2倍 到n倍筛
    {
        if (!st[i]) //是质数的话
        primes[cnt ++ ] = i;//存入 再++
        for (int j = 0; primes[j] <= n / i; j ++ )//从质数primes[j]*i筛  
        {
            st[primes[j] * i] = true;//质数的倍数必然不是质数
            if (i % primes[j] == 0) break;//结束  遇到能整除质数的倍数就结束
        }
    }
}

int main() 
{
    int n; 
    cin >> n;

    get_primes(N);

    while (n -- )
    {
        ll x; 
        cin >> x;
        int t = sqrt(x);
        if ((ll)t * t == x && st[t] == false) puts("YES");
        else puts("NO");
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    int a=abs(x1-x2),b=abs(y1-y2);
    cout << max(a,b);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long LL; 
const int mod = 1e9 + 7;
int main()
{
    int n,x;
    LL ans = 1;
    unordered_map<int,int> hash;
    cin >> n;
    //因式分解：
    while(n--)
    {
        cin >> x;

        for(int i = 2;i <= x/i; ++i)
        {
            while(x % i == 0)//能被i整除
            {
                x /= i;
                hash[i] ++;//次方++
            }
        }
        if(x > 1) hash[x] ++;
    }
    for(auto i : hash)
    ans = ans*(i.second + 1) % mod;//累乘(ak+1)        每次都取模

    cout << ans;
    return 0;
}

//【法1】
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int a[N];
int n;
int main()
{
    int t;
    cin >> t;
    while (t -- )
    {
        cin >> n;
        int maxa = 0;
        for (int i = 1; i <= n; i ++ )
        {
            cin >> a[i];
            maxa = max(maxa, a[i]);//找出最大值
        }

        bool flag = true; 
        for (int i = 1; i <=n ; i ++ ) 
            if ((maxa-a[i])&1)//只要有一个数与这组数中的最大值相差为奇数就不可能了 
                    flag = false;

        if (flag) puts("YES");
        else puts("NO");
    }

    return 0;
}

----------
//【法2】
//由于奇数加2不会变成偶数 偶数加2不会变成奇数
//因此可继续简化：
//只要偶数和奇数同时存在，就永远不可能相等 
//故只需要统计奇数和偶数的个数就可以了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=30;
int n,m;//n个整数中随机选出 m 个
int way[N];
void dfs(int u,int start)//u为当前在选的第几个数,start则表示从几开始
{
    if(n-start<m-u) return ;//剪枝  如果当前比如为u=1,5-4<3-1 那么4 5 肯定不满足

    if(u==m+1)//选完了
    {
        for(int i=1;i<=m;i++)   printf("%d ",way[i]);
        puts("");
        return ;
    }

    for(int i=start;i<=n;i++)
    {
        way[u]=i;
        dfs(u+1,i+1);//选下一个数，从i+1开始
        way[u]=0;//恢复现场  (用0标记)
    }

}
int main()
{
    scanf("%d%d",&n,&m);
    dfs(1,1);
    return 0;
}

#include<iostream>
using namespace std;
const int N=110;
int f[N],w[N][N],v[N][N],s[N];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];//每组的物品数量
        for(int j=0;j<s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];//v[i][j]代表第i组，第j个数的体积
        }
    }

    //01背包问题[一维]
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            for(int k=0;k<s[i];k++)//枚举每组的物品数量
            {
                if(j>=v[i][k])
               f[j]=max(f[j],f[j-v[i][k]]+w[i][k]); 
            }
        }
    }

      cout<<f[m]<<endl;
    return 0;
}

#include<iostream>
using namespace std;
const int M=2010,N=12010;
int f[M];
int v[N],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        //1  2  4  8  16  32  64  128  256  512  1024  
        //每一个数可用2的次方的分解来表示
        //即是将数分解打包
        while(k<=s)
        {
            cnt++;
            v[cnt]=a*k;//*k份
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0)//若还有剩余
        {
            cnt++;
            v[cnt]=a*s;//*s份
            w[cnt]=b*s;
        }
    }

    n=cnt;//相当于现在有cnt件了

    //01背包问题
      for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }

    cout<<f[m]<<endl;
   return 0;
}

【暴力】
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int arr[1000000];

int main()
{
    int n, m;
    int a, b;

    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        cin >> a >> b;
        for (int j = a; j <= b; j ++ ) arr[j] ++ ;
    }

    for (int i = 1; i <= n; i ++ )
        if (!arr[i] || arr[i] > 1)//要么没浇，要么浇多了
        {
            cout << i << ' ' << arr[i];
            return 0;
        }

    puts("OK");

    return 0;
}

【差分】
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int b[N];
//b[i]记录第i天的浇水次数
int main()
{
    scanf("%d%d", &n, &m);

    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        b[l] ++, b[r + 1] -- ;//差分
    }

    for (int i = 1; i <= n; i ++ )
    {
        b[i] += b[i - 1];
        if (b[i] != 1)//不是浇一次水
        {
            printf("%d %d\n", i, b[i]);
            return 0;
        }
    }

    puts("OK");

    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int T;
int a[20];

int main()
{
    cin >> T;
    while (T --)
    {
        int n; cin >> n;

        int ans = 0;
        while (n) 
        { // 存储数位
            a[ans ++] = n % 10;//从低位开始存的
            n /= 10;
        }
        int res = 0;
        for (int i = 0; i < ans; i ++) //ans是共有多少位
            if (a[i] != 0) 
            {
                res++;//有多少位不为0就最少有多少个元素
                a[i] *= pow(10, i);
            }

        cout << res << endl;//数列长度
        for (int i = 0; i < ans; i ++) 
            if (a[i] != 0) cout << a[i] << ' ';

        cout << endl;
    }
    return 0;
}

#include<iostream>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
   cout<<(n/k+1)*k;
   return 0;
}