Problem - D - Codeforces

题意：问能否在进行K次操作的情况下，将两个数变得相同，操作为每次选择一因子，然后除该因子。

题解：要判断该数最多能进行几次除的操作，其实就是判断这个数有多少个质因子，然后判断最后最多进行的操作数和要求的操作数大小关系，其中K=1的时候要特判一下。

• 其中开始的时候一直TLE，后来发现是long long 的问题，在没必要的情况下， long long的运行速度是慢与int的，这会在数据多的时候TLE。

详情可见  performance - C++ int vs long long in 64 bit machine - Stack Overflow

#include
using namespace std;
typedef long long ll;
typedef pair pll;
const int N=1e6+10;
const ll inf=1e15;
signed main(){
int n;scanf("%d",&n);
while(n--){
int x,y,w;scanf("%d %d %d",&x,&y,&w);
if(w==1){
puts((x%y==0||y%x==0)&&x!=y?"YES":"NO");//只有当一个数是另一个数的因子，才可以
continue;
}
for(int i=2;i*i<=x;i++){ if(x%i==0){ while(x%i==0){ x/=i;w--; } } } if(x>1) w--;
if(w<=0){ printf("Yes\n");continue; } for(int i=2;i*i<=y;i++){ if(y%i==0){ while(y%i==0){ y/=i;w--; } } } if(y>1) w--;
puts(w>0?"NO":"YES");
}
}