Codeforces Round #725 (Div. 3)-D - Another Problem About Dividing Numbers

本文主要是介绍Codeforces Round #725 (Div. 3)-D - Another Problem About Dividing Numbers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接
You are given two integers a and b. In one turn, you can do one of the following operations:

Take an integer c (c>1 and a should be divisible by c) and replace a with ac;
Take an integer c (c>1 and b should be divisible by c) and replace b with bc.
Your goal is to make a equal to b using exactly k turns.

For example, the numbers a=36 and b=48 can be made equal in 4 moves:

c=6, divide b by c ⇒ a=36, b=8;
c=2, divide a by c ⇒ a=18, b=8;
c=9, divide a by c ⇒ a=2, b=8;
c=4, divide b by c ⇒ a=2, b=2.
For the given numbers a and b, determine whether it is possible to make them equal using exactly k turns.

Input
The first line contains one integer t (1≤t≤104). Then t test cases follow.

Each test case is contains three integers a, b and k (1≤a,b,k≤109).

Output
For each test case output:

“Yes”, if it is possible to make the numbers a and b equal in exactly k turns;
“No” otherwise.
The strings “Yes” and “No” can be output in any case.
Example
input
8
36 48 2
36 48 3
36 48 4
2 8 1
2 8 2
1000000000 1000000000 1000000000
1 2 1
2 2 1
output
YES
YES
YES
YES
YES
NO
YES
NO
题意：给定三个数a，b，k，有这样一种操作，让a减去a大于一的因数，或者让b减去b大于一的因数，使得a和b相等
思路：分k=1和k!=1，k!=1的时候，我们只需要计算两数最多可以减多少次，只要k小于这个数即可，所以要进行质因数分解

#include<bits/stdc++.h>
#define ll long long
#define MOD 998244353
using namespace std;
int _ok(int x,int k){for(int i=2;i*i<=x;i++){while(x%i==0){x/=i;k--;}}if(x>1)k--;return k;
}
void slove()
{ll a,b,k;cin>>a>>b>>k;if(k==1){if(max(a,b)%min(a,b)==0&&max(a,b)-min(a,b))cout<<"YES"<<endl;elsecout<<"NO"<<endl;}else{k=_ok(a,k);k=_ok(b,k);if(k>0) cout<<"NO"<<endl;else cout<<"YES"<<endl;}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin>>t;while(t--)slove();return 0;
}