Kaosar and GCD#12273

Kaosar and GCD (Editorial)

Problem Author:	AlKaosar Hussain
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution We are taking the numbers

(1 n), (2 n), \dots, (m n)

\binom{n}{1}, \binom{n}{2}, \dots, \binom{n}{m}

and we want

g cd ((1 n), (2 n), \dots, (m n)) .

\gcd\bigl(\binom{n}{1},\binom{n}{2},\dots,\binom{n}{m}\bigr).

The clean way to do this is to look at it prime by prime. Let

n = p \prod p^{e_{p}}

n = \prod_{p} p^{e_p}

be the prime factorization of $n$ . The gcd of the binomials will also be a divisor of $n$ , so it will have the form

p ∣ n \prod p^{f_{p}}

\prod_{p \mid n} p^{f_p}

for some $f_{p} \leq e_{p}$ f_p \le e_p. Our job is to find, for every prime $p$ that divides $n$ , what is the smallest power of $p$ that appears in all of

(1 n), (2 n), \dots, (m n) .

\binom{n}{1}, \binom{n}{2}, \dots, \binom{n}{m}.

That "smallest power" is exactly

f_{p} = e_{p} - ⌊ lo g_{p} m ⌋,

f_p = e_p - \bigl\lfloor \log_p m \bigr\rfloor,

but never negative (if it becomes negative, we just put $0$ ).

Why is that true? Fix a prime $p$ and suppose $n$ has $p$ -adic valuation $e$ , i.e. $n = p^{e} \cdot r$ n = p^e \cdot r with $g cd (r, p) = 1$ \gcd(r,p)=1. Now look at the binomial with $k = p^{t}$ k = p^t where

t = ⌊ lo g_{p} m ⌋ so p^{t} \leq m < p^{t + 1} .

t = \bigl\lfloor \log_p m \bigr\rfloor \quad\text{so}\quad p^t \le m < p^{t+1}.

This $k$ is inside our range $1 \leq k \leq m$ 1 \le k \le m. For this special $k$ one can check (this is a standard fact and can be proved with carries in base $p$ or by looking at factorials) that

v_{p} ((p ^{t} n)) = e - t .

v_p\bigl(\binom{n}{p^t}\bigr) = e - t.

So for this particular $k$ the power of $p$ inside $(k n)$ \binom{n}{k} is exactly $p^{e - t}$ p^{e-t}. This already shows that the gcd cannot have more than $p^{e - t}$ p^{e-t}.

The second part is that for any $k \leq m$ k \le m you cannot get a smaller $p$ -power than $e - t$ e - t. Intuitively: to "kill" more powers of $p$ in the binomial, $k$ would have to contain more factors of $p$ in $k!$ , but up to $m$ you can only gain at most $⌊ lo g_{p} m ⌋$ \lfloor \log_p m \rfloor factors from the denominator, so the exponent in the binomial stays $\geq e - ⌊ lo g_{p} m ⌋$ \ge e - \lfloor \log_p m \rfloor. Therefore the minimum over all $k \in [1, m]$ k \in [1,m] is exactly

1 \leq k \leq m min v_{p} ((k n)) = e - ⌊ lo g_{p} m ⌋ (but not below 0) .

\min_{1 \le k \le m} v_p\bigl(\binom{n}{k}\bigr) = e - \bigl\lfloor \log_p m \bigr\rfloor \quad (\text{but not below }0).

Putting this together over all primes dividing $n$ , we get

1 \leq k \leq m g cd (k n) = p^{e} ∥ n \prod p^{m a x {0, e - ⌊ l o g_{p} m ⌋}} .

\gcd_{1 \le k \le m} \binom{n}{k} = \prod_{p^e \parallel n} p^{\max\{0,\, e - \lfloor \log_p m \rfloor\}}.

The code does exactly that:

factor $n$ into primes $p$ with exponents $e$ ;
for each $p$ compute $flog (m, p)$ \texttt{flog}(m,p) which is literally
$flog (m, p) = ⌊ lo g_{p} m ⌋$
\texttt{flog}(m,p) = \left\lfloor \log_p m \right\rfloor
by repeatedly dividing $m$ by $p$ ;
if $e > flog (m, p)$ e > \texttt{flog}(m,p) we multiply the answer by $p^{e - flog (m, p)}$ p^{e-\texttt{flog}(m,p)}.

Complexity is $O (n)$ \mathcal{O}(\sqrt{n}).

def flog(m,p):
    t=0
    while m>=p:
        m//=p
        t+=1
    return t

def g(n,m):
    ans=1;x=n;i=2
    while i*i<=x:
        e=0
        while x%i==0:
            x//=i
            e+=1
        if e:
            t=flog(m,i)
            if e>t: ans*=i**(e-t)
        i+=1
    if x>1:
        t=flog(m,x)
        if 1>t: ans*=x**(1-t)
    return ans

for _ in range(int(input())):
    n,m=map(int,input().split())
    print(g(n,m))

Python