题意

给你两个数\(a \ b\),每个操作是从这两个数中选择一个,然后选一个可以整除你选的数的数(假设是\(c\)),然后你可以把你选的数(假设是\(a\))变成\(\frac{a}{c}\),问你能不能经过\(k\)次操作让\(a\)和\(b\)相等

分析

发现最大操作次数是把这两个数都变成\(1\),而且每次都拿掉一个质因子,所以最大操作次数(设为\(Max\))就是把两个数质因数分解之后的幂次和.而最小操作次数,如果这两个数的质因子全都相同(也就是一个能整除另一个),那么最小操作次数是\(1\),如果这两个数相同,那么最小操作次数(设为\(Min\))就是\(0\),其他的情况下,最小操作次数就是\(2\).我们发现,如果\(Min \leq k \leq Max\),那么显然它是可以的(可以想成拿质因子的时候多拿或者少拿使得需要的次数加减\(1\)),否则就不行.
所以只要质因数分解一下就可以了.发现如果一个\(10^9\)之内的数不是质数,那么它的最大的质因子一定不会超过\(\sqrt{n}\),所以我们可以预处理把所有\(\sqrt{n}\)范围内的质数筛出来,然后用这些筛出来的质数进行质因数分解.最后,如果发现这个数还是大于\(1\),那么这个数一定是个质数,我们直接让它的质因子个数等于\(1\)即可.

代码

#include<bits/stdc++.h>
using namespace std;

const int N=4e4+10;
bool ip[N];
vector<int> prlist;
void init(){
	for(int i=2;i<N;i++)
		ip[i]=1;
	for(int i=2;i<N;i++){
		for(int j=2;i*j<N;j++)
			ip[i*j]=0;
	}
	for(int i=2;i<N;i++)
		if(ip[i])
			prlist.push_back(i);
	return;
}

int main(void){
	int T;
	init();
	scanf("%d",&T);
	while(T--){
		int a,b,k;
		int ans=0;
		scanf("%d%d%d",&a,&b,&k);
		int ra=a,rb=b;
		for(int i=0;i<prlist.size();i++){
			int j=prlist[i];
			while(a%j==0) {
				ans++;
				a/=j;
			}
			while(b%j==0){
				ans++;
				b/=j;
			}
		}
		if(a!=1)
			ans++;
		if(b!=1)
			ans++;
		if(k<=ans){
			if(k>=2)
				puts("YES");
			else {
				if((ra%rb==0||rb%ra==0)&&ra!=rb)
					puts("YES");
				else 
					puts("NO");
			}
		}
		else 
			puts("NO");
	}
	return 0;
}