[BOJ 18496] Euclid's Algorithm

이 문제의 목표는 모든 자연수 $a$에 대해서 $(a+d)^{k}-a^{k}$를 나누는 가장 큰 자연수($N$)를 구하는 것입니다.

• $N$은 $d$의 소인수들의 구성으로만 이루어져 있다.

어떤 소수 $p$가 존재하고 $p |N$이라고 합시다. 그럼 다음을 만족합니다.

$$(a+d)^{k} \equiv a^{k} \pmod{p}$$

$$d \equiv 0 \pmod{p}$$

따라서 $p$는 $d$의 소인수입니다.

 

$p$가 $d$의 소인수인 것은 알았지만 $(a+d)^{k}-a^{k}$이 몇 번 $p$로 나누어 떨어지는 지는 아직 모릅니다. 이 문제를 해결하기 위해서 Lifting-the-exponent lemma를 사용하였습니다.

 

Lifting-the-exponent lemma

$v_{p}(n)$는 $p^{k}|n$이고 $p^{k+1} \nmid n$인 $k$를 의미합니다. 즉, $v_{p}(n)=k$입니다.

홀수인 소수 $p$와 자연수 $x, y$에 대해 $p \nmid x$, $p \nmid y$, $p \mid (x-y)$이면 

$$v_{p}(x^{n}-y^{n})=v_{p}(x-y)+v_{p}(n)$$

$p=2$와 $x, y$에 대해 $p \nmid x$, $p \nmid y$, $p \mid (x-y)$이면

$$v_{2}(x^{n}-y^{n})=v_{2}(x-y)+v_{2}(n)+v_{2}(x+y)-1$$

 

위 보조정리를 증명하면서 문제에 적용해봅시다.

• $p \nmid x$, $p \nmid y$, $p \mid (x-y)$이고 $gcd(n,p)=1$일때 $v_{p}(x^{n}-y^{n})=v_{p}(x-y)$이다.

$p \nmid x$, $p \nmid y$, $p \mid (x-y)$ 이 조건을 통해서

$x \equiv y \pmod{p}$라는 것을 확인할 수 있습니다.

$x^{n}-y^{n}=(x-y)(x^{n-1}+x^{n-2}y+...+y^{n-1})$입니다. $(x^{n-1}+x^{n-2}y+...+y^{n-1})$가 $p$로 나누어 떨어지지 않음을 보이면 증명이 끝납니다.

$$x^{n-1}+x^{n-2}y+...+y^{n-1} \equiv nx^{n-1} \pmod{p}$$

$p \nmid n$이며 $p \nmid x$이므로 위 식은 $p$로 나누어 떨어지지 않습니다. 따라서

$$v_{p}(x^{n}-y^{n})=v_{p}(x-y)$$

 

• $p$는 홀수인 소수이고 $p \nmid x$, $p \nmid y$, $p \mid (x-y)$일 때 $v_{p}(x^{p}-y^{p})=v_{p}(x-y)+1$

$x=y+kp$라고 둡시다.

$$(y+kp)^{p}-y^{p}=kp((y+kp)^{p-1}+(y+kp)^{p-2}y+...+y^{p-1})=kpA$$

식 $A$를 전개를 시켰을 때 $p$개의 $y^{p-1}$이 존재함을 알 수 있습니다. 그리고 남은 식들 역시 $p$로 나누어 떨어집니다. 식 $A$에서 $p$를 꺼내주면

$$y^{p-1}+ky^{p-2}((p-1)+(p-2)+...+1)+pB=y^{p-1}+ky^{p-2}\frac{p(p-1)}{2}+pB$$

$p$는 홀수인 소수이므로 $\frac{p(p-1)}{2}$가 $p$로 나누어 떨어짐을 알 수 있습니다. 반면 $y^{p-1}$은 $p$로 나누어 떨어지지 않으므로 식 $A$는 $p$로 1번 나누어 떨어지게 됩니다. 따라서

$$v_{p}(x^{p}-y^{p})=v_{p}(x-y)+1$$

 

• $p$는 홀수인 소수이고 $p \nmid x$, $p \nmid y$, $p \mid (x-y)$일 때 $v_{p}(x^{n}-y^{n})=v_{p}(x-y)+v_{p}(n)$

$n=p^{a}b$이고 $p \nmid b$라고 합시다.

$$v_{p}(x^{n}-y^{n})=v_{p}(x^{p^{a}b}-y^{p^{a}b})=v_{p}((x^{p^{a}})^{b}-(y^{p^{a}})^{b})$$

1번에서 보인 것에 의해 

$$=v_{p}(x^{p^{a}}-y^{p^{a}})$$

$$=v_{p}((x^{p^{a-1}})^{p}-(y^{p^{a-1}})^{p})$$

2번에서 보인 것에 의해

$$=v_{p}(x^{p^{a-1}}-y^{p^{a-1}})+1$$

이 과정을 반복하면

$$=v_{p}(x-y)+a=v_{p}(x-y)+v_{p}(n)$$

 

• $p$는 2이고 $p \nmid x$, $p \nmid y$, $p \mid (x-y)$일 때 $v_{p}(x^{p}-y^{p})$는?

앞의 논의와 마찬가지로 $x=y+2k$라고 정의하면

$$(y+2k)^2-y^2=2k(2y+2k)$$

$$v_{2}((y+2k)^2-y^2)=v_{2}(x-y)+1+v_{2}(y+k)$$

$k=(x-y)/2$이므로 $v_{2}(y+k)=v_{2}((x+y)/2)=v_{2}(x+y)-1$이 됩니다. 따라서

$$v_{2}(x^2-y^2)=v_{2}(x-y)+v_{2}(x+y)$$

 

• $p$는 2이고 $p \nmid x$, $p \nmid y$, $p \mid (x-y)$일 때 $v_{p}(x^{n}-y^{n})$는?

$n=2^{a}b$이고 $2 \nmid b$라고 합시다.

$$v_{2}(x^{n}-y^{n})=v_{2}(x^{2^{a}b}-y^{2^{a}b})=v_{2}((x^{2^{a}})^{b}-(y^{2^{a}})^{b})$$

1번에서 보인 것에 의해 

$$=v_{2}(x^{2^{a}}-y^{2^{a}})$$

$$=v_{2}((x^{2^{a-1}})^{2}-(y^{2^{a-1}})^{2})$$

$$=v_{2}(x^{2^{a-1}}+y^{2^{a-1}})+v_{2}(x^{2^{a-1}}-y^{2^{a-1}})$$

$$=\sum_{i=0}^{a-1} v_{2}(x^{2^{i}}+y^{2^{i}}) + v_{2}(x-y)$$

이제 저 합을 간단히 하고 싶은 마음이 듭니다.

 

$x=2^{k}a+q$, $y=2^{k}b+2^{i}u-q$($2^{k}b \ge 2^{i}u$, $q,i$는 자연수)으로 둘 수 있습니다. 쉬운 $v_{2}(x+y)$부터 계산해볼까요?

$x+y=2^{k}(a+b)+2^{i}u$입니다. 따라서 $v_{2}(x+y)=i$. 이 뒤의 경우($v_{2}(x^{2^{i}}+y^{2^{i}})$, $i \ge 1$)는 모두 한가지 값으로 확정지을 수 있습니다. 위 경우를 살펴보면 오직 상수항의 영향을 받아 $v_{2}$값이 정해지는 것을 알 수 있습니다. $x^{2^{i}}+y^{2^{i}}$의 상수항 부분만 알아보자면 $q^{2^{i}}+(2^{i}u-q)^{2^{i}}$이 됩니다. 만약 이 친구들이 4로 나누어 떨어진다면 $v_{2}$가 2이상의 값을 가지게 됩니다. 

$$q^{2^{i}}+(2^{i}u-q)^{2^{i}} \equiv q^{2^{i}}+q^{2^{i}} \not\equiv 0 \pmod{4}$$

따라서 $v_{2}(x^{2^{i}}+y^{2^{i}})$의 값은 $i \ge 1$일 때는 전부 1입니다. $i=0$일 때는 $v_{2}(x+y)$입니다.

$$v_{2}(x^{n}-y^{n})=v_{2}(x-y)+v_{2}(n)+v_{2}(x+y)-1$$

지금까지는  $p \nmid x$, $p \nmid y$인 경우에 대해서 알아보았습니다. 문제에서 요구하는 것은 모든 자연수 $a$에 대한 것입니다. $a+d$가 $p$로 나누어질 수도 있고 아닐 수도 있죠. 그러니 지금부터는 $p$로 나누어지는 경우를 알아보겠습니다.

 

• $p$는 소수일 때 $v_{p}(x^{n}-y^{n})$의 최솟값은 무엇인가?

우리는 여러 케이스에서 나오는 값들 중 최솟값을 찾을 것입니다. 가장 작은 값이 문제의 답이 될 것이기 때문입니다.(문제에서 구하라는 최댓값과 햇갈리면 안됩니다.) 문제의 상황에 맞추겠습니다.

$a=p^{k}s$, $p \nmid s$이며 $d=p^{l}t$, $p \nmid t$라고 합시다. ($k$는 0 이상의 정수, $l,s,t$는 자연수)

- $k>l$

$$x^{n}-y^{n}=p^{ln}((p^{k-l}s+t)^{n}-(p^{k-l}s)^{n})=p^{ln}A$$

$$v_{p}(x^{n}-y^{n})=ln$$

- $k=l$

$$x^{n}-y^{n}=p^{ln}((s+t)^{n}-s^{n})=p^{ln}A$$

$p$가 $s+t$를 나누던 나누지 않던 결과는 같습니다.

$$v_{p}(x^{n}-y^{n})=ln$$

- $k<l$

$$x^{n}-y^{n}=p^{kn}((s+p^{l-k}t)^{n}-s^{n})=p^{kn}A$$

$$v_{p}(x^{n}-y^{n})=kn+l-k+v_{p}(n)$$

$k$의 값은 고정된 값이 아니므로 마음대로 바꿀 수 있습니다. 최솟값을 만들어야하니 $k=0$을 주도록 합시다.

$$v_{p}(x^{n}-y^{n})=l+v_{p}(n)$$

다만 $p=2$이고 $x+y \equiv 0 \pmod{4}$일 경우 $+v_{2}(x+y)-1$을 해주어야 된다는 사실을 확인해야 합니다.

 

이제 $p$에 따라 최솟값이 무엇인지 알아봅시다.

• $p$가 홀수인 소수

$ln \le l+v_{p}(n)$이라 합시다. $n$의 가장 작은 값인 $p$를 넣어봅시다.

$pl \le l+1$이며 이는 $l>0$인 조건에 어긋납니다. $n$을 점점 증가시키면 $v_{p}(n)$의 증가속도가 $n$의 증가속도를 따라잡을 수 없어 이 역시 조건에 어긋나게 됩니다. 따라서 $ln > l+v_{p}(n)$이 성립하며 최솟값은 $l+v_{p}(n)$입니다.

 

• $p$는 2

$l=1$인 경우 $d \bmod{4}=2$가 성립합니다.

$n=2$이면 최솟값은 $v_{2}(x+y)=v_{2}(2a+d)=2$을 고려하지 않은 $v_{p}(d)+v_{p}(n)$임을 알 수 있습니다.

$n \ge 4$이고 $n$이 짝수이면 최솟값은 $v_{2}(x+y)=v_{2}(2a+d)=2$을 고려한 $v_{p}(d)+v_{p}(n)+1$임을 알 수 있습니다. 홀수라면 $v_{p}(d)+v_{p}(n)$입니다.

$l \ge 2$인 경우 최솟값은 항상 $v_{p}(d)+v_{p}(n)$임을 확인할 수 있습니다.

 

문제에 맞춰 지금까지의 내용을 정리해봅시다.

$p$가 홀수인 소수일 때 $v_{p}(x^{n}-y^{n})=v_{p}(d)+v_{p}(n)$

$p$가 짝수일 때 

- $n \ge 4$, $n$은 짝수이고 $d \bmod{4}=2$이면 $v_{p}(x^{n}-y^{n})=v_{p}(d)+v_{p}(n)+1$

- 위의 경우가 아니면 $v_{p}(x^{n}-y^{n})=v_{p}(d)+v_{p}(n)$

 

이제 계산만 하면 됩니다! ㅎㅎ 가장 간단하게 생각할 수 있는 것은 $d$의 소인수를 찾고 그걸로 $k$를 나눠보고 하는 것입니다. 하지만 $10^{100}$이나 되는 수를 소인수분해 하기란 참 어려운 일입니다. $d$의 소인수를 만약 찾았다고 하면 어차피 $v_{p}(d)$의 값이 꾸준히 등장하기 때문에 문제의 정답은 결국 $d$의 배수가 됩니다. 따라서 $v_{p}(d)$의 값을 따로 계산할 이유가 없습니다. 그럼 $v_{p}(k)$의 값을 생각해보아야 합니다. 이는 결국 $d$의 소인수가 $k$에 얼마나 들어있냐?와 같은 말입니다. 따라서 $gcd(d,k)$를 계산하고 $k$를 $gcd(d,k)$로 나누는 작업울 꾸준히 반복하면 $k$에서 $d$의 소인수를 전부 꺼낼 수 있게 됩니다. 소인수분해가 필요 없죠!

 

이 길고 긴 여정의 끝에 200바이트 정도 되는 코드를 만날 수 있습니다! 껄껄

코드 보기

def gcd(d, k):
    if k == 0:
        return d
    return gcd(k, d % k)
 
d, k=map(int, input().split())
h = k
s = d
while 1:
    g = gcd(d, h)
    if g == 1:
        break
    h //= g
    s *= g
 
if d % 4 == 2 and k % 2 == 0 and k >= 4:
    s *= 2
print(s)