Kaosar və GCD#12273

Kaosar və GCD (Həll təhlili)

Problemin Müəllifi:	AlKaosar Hussain
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll Biz aşağıdakı ədədləri götürürük:

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

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

və biz istəyirik

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

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

Bunu etmək üçün təmiz yol, onu ilk ədəddən-ədədə nəzərdən keçirməkdir. Tutaq ki,

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

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

$n$ -nin ilkin faktorizasiyasıdır. Binomların gcd-si də $n$ -nin bir böləni olacaq, buna görə də onun forması olacaq

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

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

bəziləri üçün $f_{p} \leq e_{p}$ f_p \le e_p. Bizim işimiz, $n$ -ni bölən hər bir ilkin ədəd $p$ üçün, hamısında görünən $p$ -nin ən kiçik gücünü tapmaqdır

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

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

O "ən kiçik güc" tam olaraq

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

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

amma heç vaxt mənfi olmur (əgər mənfi olarsa, sadəcə $0$ qoyuruq).

Bu niyə doğrudur? Bir ilkin ədəd $p$ götürün və $n$ -nin $p$ -adic qiymətləndirməsi $e$ olduğunu düşünün, yəni $n = p^{e} \cdot r$ n = p^e \cdot r və $g cd (r, p) = 1$ \gcd(r,p)=1. İndi $k = p^{t}$ k = p^t olan binomiyaya baxın, burada

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

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

Bu $k$ bizim aralığımızdadır $1 \leq k \leq m$ 1 \le k \le m. Bu xüsusi $k$ üçün yoxlamaq olar (bu standart bir faktdır və $p$ -dəki daşımalara baxaraq və ya faktoriallara baxaraq sübut edilə bilər) ki

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

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

Beləliklə, bu xüsusi $k$ üçün $k$ -dəki $p$ -nin gücü tam olaraq $p^{e - t}$ p^{e-t}-dir. Bu artıq göstərir ki, gcd daha çox $p^{e - t}$ p^{e-t}-dən çox ola bilməz.

İkinci hissə budur ki, hər hansı $k \leq m$ k \le m üçün siz $e - t$ e - t-dən daha kiçik bir $p$ -gücü əldə edə bilməzsiniz. İntuitiv olaraq: binomda daha çox $p$ güclərini "öldürmək" üçün, $k$ $k!$ -da daha çox $p$ faktoru içərməlidir, lakin $m$ -ə qədər siz yalnız $⌊ lo g_{p} m ⌋$ \lfloor \log_p m \rfloor faktoru əldə edə bilərsiniz, buna görə də binomda olan eksponent $\geq e - ⌊ lo g_{p} m ⌋$ \ge e - \lfloor \log_p m \rfloor qalır. Buna görə də, $[1, m]$ aralığında olan bütün $k$ -lar üçün minimum tam olaraq

1 \leq k \leq m min v_{p} ((k n)) = e - ⌊ lo g_{p} m ⌋ (amma 0-dan a s ¸ a g ˘ ı deyil) .

\min_{1 \le k \le m} v_p\bigl(\binom{n}{k}\bigr) = e - \bigl\lfloor \log_p m \bigr\rfloor \quad (\text{amma $0$-dan aşağı deyil}).

Bunu $n$ -ni bölən bütün ilkin ədədlər üçün bir araya gətirdikdə, biz alırıq

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

Kod tam olaraq bunu edir:

$n$ -ni $p$ -lərə və $e$ -lərə ayırın;
hər bir $p$ üçün $flog (m, p)$ \texttt{flog}(m,p)-ni hesablayın ki, bu da tam olaraq
$flog (m, p) = ⌊ lo g_{p} m ⌋$
\texttt{flog}(m,p) = \left\lfloor \log_p m \right\rfloor
$m$ -ni $p$ -yə təkrarlayaraq bölməklə;
əgər $e > flog (m, p)$ e > \texttt{flog}(m,p)-dirsə, cavabı $p^{e - flog (m, p)}$ p^{e-\texttt{flog}(m,p)} ilə vururuq.

Komplekslik $O (n)$ \mathcal{O}(\sqrt{n})-dir.

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