Links:

Contest
Problem

Author, Tester and Editorialist: Vedang Dadape

Difficulty:

Hard

Prerequisites:

• Legendre's Formula
• Prime Factorization
• Exponents

Problem:

The Yovo fruit grows on the Home Tree in Pandora. Every day, the number of Yovo fruits gets multiplied by the age of the Home Tree(in days).

Ex: If $$$Y_{n}$$$ denotes the number of Yovo fruits on the $$$n_{th}$$$ day, then $$$Y_{n} = Y_{n-1} * n.$$$

It is a fact that the Home Tree had 1 fruit on its first day.

You want to distribute these Yovo fruits with entire Na'vi population such that each individual gets equal amount of fruits. Is this possible?

Input Format:

First line will contain T, number of test cases. Then the test cases follow. Each line contains two space-separated integers N, the age of the Home Tree(in days), and K, the entire Na'vi population.

Constraints:

$$$1 \leq$$$ $$$T$$$ $$$\leq 10$$$

Test Set 1

• $$$1 \leq$$$ $$$N$$$ $$$\leq 20$$$ , $$$1 \leq$$$ $$$K$$$ $$$\leq 10^{14}$$$

Test Set 2

• $$$1 \leq$$$ $$$N$$$ $$$\leq 10^{6}$$$ , $$$1 \leq$$$ $$$K$$$ $$$\leq 10^{14}$$$

Test Set 3

• $$$1 \leq$$$ $$$N$$$ $$$\leq 10^{14}$$$ , $$$1 \leq$$$ $$$K$$$ $$$\leq 10^{14}$$$

Output Format:

For each test case, output "YES" (without the quotation marks and in upper case) if it is possible to distribute the fruits equally among the entire Na'vi population otherwise output "NO" (without the quotation marks and in upper case)

Explanation:

Basically, We have to find out if N factorial is divisible by K.

Legendre's formula gives us the exponent of the largest power of a prime number $$$p$$$ that divides $$$n!$$$. Note: The number $$$p$$$ must be prime. Let $$$V_{p}n$$$ be the exponent of the largest power of $$$p$$$ that divides $$$n$$$. Then,

We can stop when $$$p^{i} \gt n$$$ since the value of $$$\displaystyle\sum_{j=i}^\infty\Bigl\lfloor\dfrac{n}{p^{j}}\Bigr\rfloor$$$ will always be $$$0$$$.

Now, since $$$K$$$ is not necessarily prime and can be composite, We have to calculate exponents of largest power of all prime factors of $$$K$$$ that divides $$$N!$$$ and floor divide it by exponents of those prime factors in prime factorization of $$$K$$$.

Let factorization of $$$K = p_1^{x_1} p_2^{x_2} \cdot \ldots \cdot p_m^{x_m}$$$. For each $$$p_{i}$$$ we calculate the the number of times it is present in $$$n!$$$ using Legendre's formula described above — let's call this value $$$y_{i}$$$. We floor divide this value by $$$x_{i}$$$ — let's call this value $$$A_{i}$$$

The highest power of composite $$$K$$$ will be $$$\displaystyle\min_{i=1 \ldots m} A_i = \min_ {i=1 \ldots m} \Bigl\lfloor\dfrac{y_{i}}{x_{i}}\Bigr\rfloor$$$

If this highest power of $$$K$$$ in $$$N!$$$ is greater than 0, then $$$N!$$$ is divisible by $$$K$$$.
Output YES if $$$N!$$$ is divisible by $$$K$$$, otherwise output NO.

Time Complexity:

$$$O(\sqrt{k}*\log_{k}n)$$$ for each test case.

Code:

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

ll largestPowerOfPrimeInFactorial(ll n, ll p)
{
    ll res = 0;
    while (n)
    {
        n /= p;
        res += n;
    }
    return res;
}

ll largestPowerOfCompositeInFactorial(ll n, ll k)
{
    ll res = LLONG_MAX;
    ll ct = 0;
    if (k % 2 == 0)
    {
        while (k % 2 == 0)
        {
            k /= 2;
            ct++;
        }
        res = min(res, largestPowerOfPrimeInFactorial(n, 2) / ct);
    }
    for (ll i = 3; i * i <= k; i += 2)
    {
        if (k % i == 0)
        {
            ct = 0;
            while (k % i == 0)
            {
                k /= i;
                ct++;
            }
            res = min(res, largestPowerOfPrimeInFactorial(n, i) / ct);
        }
    }
    // If k is prime
    if (k > 2)
        res = min(res, largestPowerOfPrimeInFactorial(n, k));
    return res;
}

int main()
{
    ll t;
    cin >> t;
    while (t--)
    {
        ll n, k;
        cin >> n >> k;
        assert(n > 0 && k > 0 && n <= (ll)(1e14) && k <= (ll)(1e14));
        cout << (largestPowerOfCompositeInFactorial(n, k) > 0 ? "YES" : "NO") << '\n';
    }
}