Каосар і НСД#12273

Каосар і НСД (Розбір)

Автор проблеми:	AlKaosar Hussain
Підготовлено:	Hasan Saleh (MathModel)
Редагував:	Hasan Saleh (MathModel)

Рішення Ми беремо числа

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

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

і хочемо

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

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

Чистий спосіб зробити це - подивитися на це простими числами. Нехай

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

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

буде простим розкладом $n$ . НСД біноміальних коефіцієнтів також буде дільником $n$ , отже, він матиме форму

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

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

для деяких $f_{p} \leq e_{p}$ f_p \le e_p. Наша задача - знайти для кожного простого числа $p$ , яке ділить $n$ , яка найменша степінь $p$ , що з'являється в усіх

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

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

Ця "найменша степінь" є точною

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

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

але ніколи не від'ємною (якщо вона стає від'ємною, ми просто ставимо $0$ ).

Чому це правда? Фіксуємо просте число $p$ і припустимо, що $n$ має $p$ -адичну оцінку $e$ , тобто $n = p^{e} \cdot r$ n = p^e \cdot r з $g cd (r, p) = 1$ \gcd(r,p)=1. Тепер подивіться на біноміальний коефіцієнт з $k = p^{t}$ k = p^t, де

t = ⌊ lo g_{p} m ⌋ так що p^{t} \leq m < p^{t + 1} .

t = \bigl\lfloor \log_p m \bigr\rfloor \quad\text{так що}\quad p^t \le m < p^{t+1}.

Цей $k$ знаходиться в нашому діапазоні $1 \leq k \leq m$ 1 \le k \le m. Для цього спеціального $k$ можна перевірити (це стандартний факт і може бути доведено з перенесеннями в основі $p$ або шляхом розгляду факторіалів), що

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

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

Отже, для цього конкретного $k$ степінь $p$ всередині $(k n)$ \binom{n}{k} є точною $p^{e - t}$ p^{e-t}. Це вже показує, що НСД не може мати більше, ніж $p^{e - t}$ p^{e-t}.

Друга частина полягає в тому, що для будь-якого $k \leq m$ k \le m ви не можете отримати меншу степінь $p$ , ніж $e - t$ e - t. Інтуїтивно: щоб "вбити" більше степенів $p$ в біноміальному коефіцієнті, $k$ повинен містити більше факторів $p$ в $k!$ , але до $m$ ви можете отримати максимум $⌊ lo g_{p} m ⌋$ \lfloor \log_p m \rfloor факторів з знаменника, тому показник у біноміальному коефіцієнті залишається $\geq e - ⌊ lo g_{p} m ⌋$ \ge e - \lfloor \log_p m \rfloor. Отже, мінімум для всіх $k \in [1, m]$ k \in [1,m] є точно

1 \leq k \leq m min v_{p} ((k n)) = e - ⌊ lo g_{p} m ⌋ (але не нижче 0) .

\min_{1 \le k \le m} v_p\bigl(\binom{n}{k}\bigr) = e - \bigl\lfloor \log_p m \bigr\rfloor \quad (\text{але не нижче }0).

Збираючи це разом для всіх простих чисел, що ділять $n$ , ми отримуємо

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\}}.

Код робить саме це:

розкладає $n$ на прості числа $p$ з показниками $e$ ;
для кожного $p$ обчислює $flog (m, p)$ \texttt{flog}(m,p), що буквально є
$flog (m, p) = ⌊ lo g_{p} m ⌋$
\texttt{flog}(m,p) = \left\lfloor \log_p m \right\rfloor
шляхом повторного ділення $m$ на $p$ ;
якщо $e > flog (m, p)$ e > \texttt{flog}(m,p), ми множимо відповідь на $p^{e - flog (m, p)}$ p^{e-\texttt{flog}(m,p)}.

Складність становить $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