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

给三个数,a,b,k, 问a和b是不是能在k次(exactly) 下通过整除相等.

这个题情况比较多, 比如a和b互质, 比如k大于a和b. 反正就是交一次就对的都是大神.

这题思路是, 反正a和b一直和某数做整除, 最后就是1, 肯定相等啊, 所以只需要计算有多少质因子在a和b的和中.即可, 剩下就是各种corner cases.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);  
    int t;
    cin >> t;
    while (t --)
    {
        auto gcd = [&](auto wtf, int a, int b) -> int {
        if(b == 0)
            return a;
        return wtf(wtf, b, a % b);
        }; 
        auto fac = [&](int n) -> int {
            int res = 0;
            for (size_t i = 2; i * i <= n; i++)
            {
                while (n % i == 0)
                {
                    res++;
                    n /= i;
                }
            }
            if (n > 1) // if n is a prime, but not 1
            {
                res++;
            }
            return res;
        };
        int a,b,k;
        cin >> a >> b >> k;
      //  cout << fac(a) << endl;
      //  cout << fac(b) << endl;
        if (k == 1)
        { 
            int g = gcd(gcd, a, b);
            if ((g == a || g == b) && a != b)
            {
                cout << "YES" << endl;
            }
            else
            {
                cout << "NO" << endl;
            }
        }
        else if (k > 1)
        {
            if (k > fac(a) + fac(b))
            {
                cout << "NO" << endl;
            }
            else
            {
                cout << "YES" << endl;
            }
        }
    } 
    
  
    
    return 0;
}