Oppa Funcan Style Remastered
Contest: Codeforces Round 485 (Div. 1)
Difficulty rating: 3300
Tags: graphs, math, number theory, shortest paths

Surely you have seen insane videos by South Korean rapper PSY, such as "Gangnam Style", "Gentleman" and "Daddy". You might also hear that PSY has been recording video "Oppa Funcan Style" two years ago (unfortunately we couldn't find it on the internet). We will remind you what this hit looked like (you can find original description here):

On the ground there are $$$n$$$ platforms, which are numbered with integers from $$$1$$$ to $$$n$$$, on $$$i$$$-th platform there is a dancer with number $$$i$$$. Further, every second all the dancers standing on the platform with number $$$i$$$ jump to the platform with the number $$$f(i)$$$. The moving rule $$$f$$$ is selected in advance and is not changed throughout the clip.

The duration of the clip was $$$k$$$ seconds and the rule $$$f$$$ was chosen in such a way that after $$$k$$$ seconds all dancers were in their initial positions (i.e. the $$$i$$$-th dancer stood on the platform with the number $$$i$$$). That allowed to loop the clip and collect even more likes.

PSY knows that enhanced versions of old artworks become more and more popular every day. So he decided to release a remastered-version of his video.

In his case "enhanced version" means even more insanity, so the number of platforms can be up to $$$10^{18}$$$! But the video director said that if some dancer stays on the same platform all the time, then the viewer will get bored and will turn off the video immediately. Therefore, for all $$$x$$$ from $$$1$$$ to $$$n$$$ $$$f(x) \neq x$$$ must hold.

Big part of classic video's success was in that looping, so in the remastered version all dancers should return to their initial positions in the end of the clip as well.

PSY hasn't decided on the exact number of platforms and video duration yet, so he asks you to check if there is a good rule $$$f$$$ for different options.

Input format:
In the first line of input there is one integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of options for $$$n$$$ and $$$k$$$ to check.

In the next $$$t$$$ lines the options are given: each option is described with two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^{18}$$$, $$$1 \le k \le 10^{15}$$$) — the number of dancers and the duration in seconds.

It is guaranteed that the number of different values of $$$k$$$ in one test is not greater than $$$50$$$.

Output format:
Print $$$t$$$ lines. If the $$$i$$$-th option of the video is feasible, print "YES" (without quotes) in $$$i$$$-th line, otherwise print "NO" (without quotes).

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
3
7 7
3 8
5 6

Example output:
YES
NO
YES

Editorial:
Let's understand the problem first. The rule $$$f(x)$$$ must be bijective, because otherwise some platforms will be empty in $$$k$$$ seconds. So we are looking for permutations $$$p$$$ of size $$$n$$$. Let's say that cycles of the permutation have lengths $$$c_1, c_2, \ldots, c_m$$$. $$$p^k$$$ is an identity permutation if and only if $$$c_i$$$ divides $$$k$$$ for all $$$i$$$. Also $$$c_i \ne 1$$$. So, we need to check if there are such numbers $$$c_i$$$ for which all these holds:
• $$$n = \sum c_i$$$
• $$$c_i \ne 1$$$
• $$$c_i$$$ is a divisor of $$$k$$$
It is not profitable to use composite divisors of $$$k$$$ because we can substitute each of them with any its prime divisor repeated necessary number of times.
Let's say that $$$p_1 < p_2 < \ldots < p_m$$$ — the list of all distinct prime divisors of $$$k$$$. Then the problem is essentially: Check if there are nonnegative coefficients $$$b_i$$$ such that $$$n = \sum b_i \cdot p_i$$$.
If $$$m=0$$$ ($$$k=1$$$) answer is NO.
If $$$m=1$$$, then the answer is YES if and only if $$$n$$$ is divisible by $$$p_1$$$.
If $$$m=2$$$, then you have to say if there is a nonnegative solution to Diophantine equation. It can be done using extended Euclid algorithm.
And if $$$m \ge 3$$$, then $$$p_1 \le k^{1/m} \le k^{1/3} \le 10^5$$$. Let's find $$$d(r)$$$ — the minimal number equal to $$$r$$$ modulo $$$p_1$$$ that can be written in form $$$\sum b_i \cdot p_i$$$. If we do this, the answer is obvious: YES if and only if $$$n \ge d(n \mod p_1)$$$. To find all the $$$d$$$ we'll build a directed graph. It's vertices are the remainders modulo $$$p_1$$$, and there is a directed edge from $$$x$$$ to $$$(x + p_i) \mod p_1$$$ with weight $$$p_i$$$ for all $$$x$$$ and $$$i$$$. Let's see that the path from $$$0$$$ in this graph is a set of $$$p_i$$$, its weight is the sum of $$$p_i$$$ and it leads to a remainder of this sum modulo $$$p_1$$$. Therefore, $$$d(r)$$$ is shortest path from $$$0$$$ to $$$r$$$ in this graph. There are $$$p_1$$$ vertices and $$$p_1 \cdot m$$$ edges in this graph, so dijkstra's running time is $$$O(mp_1 \log p_1) = O(m k^{1/m} \log (k^{1/m})) = O(k^{1/m} \log k) = O(k^{1/3} \log k)$$$.
We also need to factorize $$$k$$$. Let's build sieve once and find all the primes up to $$$\sqrt{K}$$$ ($$$K=10^{15}$$$). Then we can factorize numbers up to $$$K$$$ in $$$O(\frac{\sqrt{K}}{\log K})$$$ just like in trivial $$$O(\sqrt{K})$$$ algorithm but trying only prime divisors.
Let's calculate complexity now. Let's say that number of all tests is $$$t \le 10^4$$$ and number of different $$$k$$$ is $$$q \le 50$$$. Solutions for $$$m=1$$$ and $$$m=2$$$ works in $$$O(1)$$$ and $$$O(\log n)$$$ time, so total time is $$$O(t \log n)$$$. Solution for $$$m \ge 3$$$ works in $$$O(k^{1/3} \log k)$$$, but this dijkstra should be done once for each $$$k$$$, for different $$$n$$$ we should only check one condition using calculated distances. Therefore, total time for these solutions is $$$O(q k^{1/3} \log k + t)$$$. Also there is sieve in $$$O(\sqrt{K} \log \log K)$$$ and factorization in $$$O(\frac{\sqrt{k}}{\log k})$$$ $$$q$$$ times.
Total complexity — $$$O(\sqrt{K} \log \log K + q (\frac{\sqrt{k}}{\log k} + k^{1/3} \log k) + t \log n)$$$.