CF1538D Another Problem About Dividing Numbers

传送门

题目大意

给 $a$，$b$，$k$ 三个数在 $k$ 次操作后 $a=b$，输出 YES，否则输出 NO，每次操作可以让 $a$ 或 $b$ 整除一个大于 $1$ 的整数。

---

分析

我们看这道题结合样例不难发现，我们可以求出一个范围，只要 $k\in[\min,\max]$ ，反之则不行。

那么我们先找范围 $\min$，首先我们知道两个不为 $1$ 的数， $k=2$ 是一定可以：可以让 $\frac{a}{a}=1$，再 $\frac{b}{b}=1$ 即可。

而如果 $a\mid b$ 或 $b\mid a$，$k_{\min}=1$，让大的数除到小的数即可 。

接着我们要找范围 $\max$，我们可以先将两个数的最大公约数求出，设 $f_i$ 为数的分解质因数后的质因数个数，这样我们可以求最大值了。

例子：

$4,4$

$k=2$ 时：$2,2$

$k=3$ 时：$1,1$

$k=3$ 时，因为每次可以除大于 $1$ 的整数，所以最大值可以是 $2\times f_i(\gcd(a,b))$（$a$ 贡献一次，$b$ 贡献一次）。

但这并不全面，因为我们让 $a$ 和 $b$ 直接除到他们的最大公因数，而在 $a$ 和 $b$ 除时，除的数也可以贡献最大值。

例子：

$36,48$

$a=12$ 和 $b=12$ 时，$\frac{a}{3}=12$，$\frac{b}{4}=12$，而 $4=2\times 2$，可以为最大值贡献 $2$。

所以 $\max={2\times f_i(\gcd(a,b))+f_i(\frac{a}{\gcd(a,b)})+f_i(\frac{b}{\gcd(a,b)})}$

---

代码

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cmath>
using namespace std;
int t;//t组数据
int a,b,k; 
int m_i,m_a;//可以满足的最小值和最大值 
int gcd(int a,int b){//最大公约数 
  if(!b){
    return a;
  }
  gcd(b,a%b);
}
int f_i(int a){//分解质因子，求质因子的数量 
  int n_n=0;
  int a_a=a;
  for(int i=2;i*i<=a_a;i++){
    if(a==1)break;
    if(a%i==0){
      while(a%i==0){
        a/=i;n_n++;
      }
    }
  }
    if(a>1)n_n++;
  return n_n;
}
int main(){
  scanf("%d",&t);
  while(t--){
    scanf("%d %d %d",&a,&b,&k);
    if(a<b)swap(a,b);//方便求最大公约数 
    int g_c=gcd(a,b);
    if((g_c==a||g_c==b)&&a!=b)m_i=1;//特判 
    else m_i=2;
    m_a=2*f_i(g_c)+f_i(a/g_c)+f_i(b/g_c);//求k最大可以是多少 
    if(k>=m_i&&k<=m_a)cout<<"YES"<<endl;//输出 
    else cout<<"NO"<<endl;
  }
  return 0; 
}