我不会分讨。
可以知道一个美丽数 \(a\) 的充要条件是 \(a=d\times k\) 且 \(d\nmid k\)。
有个朴素的想法是将给你的 \(x\) 拆成 \(d^p\times k\)。
- 显然如果 \(p\le 1\) 那么我们拆不动。
- 如果 \(k\) 可以拆成大于 \(2\) 个数的乘积，那么是可行的。
- 如果 \(k\) 是质数，那么我们就拆 \(d\)。
- 如果 \(d\) 是质数，就拆不了了。
- 如果 \(d\) 不是质数：
- 如果有个不是 \(k\) 的质因子，那么是可行的。
- 如果 \(k=1\)，那么是不可行的。
- 现在 \(d=k^q\)。
- 如果 \(d=k^2\) 且 \(p>3\)，那么可行；
- 如果 \(q>2\) 且 \(p>2\)，那么可行。
点击查看代码
#include<bits/stdc++.h>
#define int ll
#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define inn(i,n,a) For(i,1,n) a[i]=read();
#define ll long long
#define i128 __int128
using namespace std;
inline int read() {
int xx= 0;int f= 1;
char c = getchar();
while(c<'0'||c>'9') {
if(c=='-') f= -1;
c= getchar();
}
while(c>='0'&&c<='9') {
xx= (xx<<1)+(xx<<3)+(c^48);
c= getchar();
}
return xx*f;
}
#define maxn 200050
int x,d;
void work() {
in2(x,d);
int cnt=0;
while(x%d==0) x/=d,cnt++;
if(cnt<2) return cout<<"NO\n",void();
for(int i=2;i*i<=x;i++) {
if(x%i==0) return cout<<"YES\n",void();
}
bool pr=1;
for(int i=2;i*i<=d;i++)
if(d%i==0) {
pr=0;
break;
}
if(pr) return cout<<"NO\n",void();
if(cnt>2) {
for(int i=2;i*i<=d;i++)
if(d%i==0&&(i!=x||(d/i!=x))) return cout<<"YES\n",void();
}
if(x==1) return cout<<"NO\n",void();
int cnt2=0;
while(d%x==0) cnt2++,d/=x;
if(cnt2>2&&cnt>2) return cout<<"YES\n",void();
if(cnt2==2&&cnt>3) return cout<<"YES\n",void();
return cout<<"NO\n",void();
}
signed main() {
int _=read();
while(_--) work();
}