ABC284D Happy New Year 2023题解
MoyunAllgorithm
·
·
题解
题意
给你正整数 N。已知 N 可以被表示为 p^2q ( p 和 q 是不相同的质数）。求 p 和 q。数据保证有解且唯一。
**给出一种时间、空间复杂度不太优秀但确实能够通过的解法。**
**第一轮**：首先，如果 $N$ 是偶数则必然含有 $2$，特判即可。
**第二轮：** 接下来，因为我们知道 $100$ 以内有哪些质数，所以接下来我们枚举 $100$ 以内的 $24$ 个奇质数，将它们作为 $p$ 和 $q$，判断。
**第三轮：** 如果 $N$ 仍然不包含上面的那些质因子，说明 $p,q >100$。 我们枚举 $p$。但是，因为 $p^2=\dfrac{N}{q}$，而 $q>100$，所以 $p$ 的范围是 $[100,\sqrt{9 \times 10^{16}}=3 \times 10^8]$。 我们提前用欧拉筛筛出 $3 \times 10^8$ 的质数（约有 $10^7$ 个），对于每个不能被 $<100$ 的质数分解的 $N$，枚举这些质数作为 $p$ 进行判断。
多组询问，$T \le 10$，时间复杂度为 $(10^8+10^7 T)$，$T \le 10$，且很多 $N$ 会在第一轮和第二轮快速筛掉而不用进行第三轮，再加上时限为 $3$ 秒，可以通过本题。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN=3e8+5;
int N,Q;
int prime[MAXN];
bool isprime[MAXN];
int tot=0;
int smallprime[30]={0,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
void EulerSieve()
{
for(int i=2;i<=MAXN-5;i++) isprime[i]=1;
for(int i=2;i<=MAXN-5;i++)
{
if(isprime[i]) prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=MAXN-5;j++)
{
isprime[i*prime[j]]=0;
if(i%prime[j]==0) break;
}
}
}
int T;
int main()
{
scanf("%d",&T);
EulerSieve();
while(T--)
{
long long N;
scanf("%lld",&N);
if(N%4==0)
{
printf("%d %lld\n",2,N/4);
continue;
}
if(N%2==0)
{
long long k=N/2;
k=sqrt(k);
printf("%lld %d\n",k,2);
continue;
}
//第一轮：筛掉偶数
bool find=0;
for(int i=1;i<=24;i++)
{
int a=smallprime[i],b=a*a;
long long k=N/a;
k=sqrt(k);
if(N%b==0) printf("%d %lld\n",a,N/b);
else if(N%a==0) printf("%lld %d\n",k,a);
if(N%b==0||N%a==0)
{
find=1;
break;
}
}
if(find) continue;
//第二轮：筛掉含有100以内质因数的数
for(int i=1;i<=tot;i++)
{
int x=prime[i];
if(N%(1ll*x*x)==0)
{
printf("%d %lld\n",x,N/(1ll*x*x));
break;
}
}
//第三轮
}
return 0;
}
```