CF 1300-2300 数论

Link

前言：太逊啦，都人均在切3000+的题，就我……

刚刚开始做……要持续更个一个月吧qwq

T1 230B T-primes

https://www.luogu.com.cn/problem/CF230B

奇数个不同的正整数因数，很明显，是完全平方数。而且 \(\sqrt{x}\) 也得是一个质数。

注意开 \(longlong\)。

#include<iostream>
#include<cstdio>
#include<string.h>
#include<math.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch==‘-‘)f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void write(int x)
{
    if(x<0) putchar(‘-‘),write(-x);
    else{if(x>9)write(x/10);putchar(‘0‘+x%10);}
}
inline void writeputs(int x){write(x),putchar(‘\n‘);}
inline void writeputchar(int x){write(x),putchar(‘ ‘);}
int t,ans_prime[100005],tot_prime;
bool if_prime[1000005];
void pre_prime(int x)
{
    memset(if_prime,1,sizeof if_prime);
    if_prime[1]=0;
    FOR(i,2,x)
    {
        if(if_prime[i]) ans_prime[++tot_prime]=i;
        FOR(j,1,tot_prime)
        {
            int y=i*ans_prime[j],z=i%ans_prime[j];
            if(y>x) break;
            if_prime[y]=0;
            if(z==0) break;
        }
    }
}
signed main()
{
    pre_prime(1000000);
    t=read();
    while(t--)
    {
        int x=read(),y=sqrt(x);
        if(!if_prime[y])
        {
            puts("NO");
            continue;
        }
        if(pow(y,2)==x)
        {
            puts("YES");
            continue;
        }
        puts("NO");
    }
    return 0;
}

CF 1300-2300 数论

原文：https://www.cnblogs.com/F-T-Y/p/13426485.html