[BOJ 20202] Euklid

일반 물리가 재미없어서 수업시간에 푼 문제;; 아~ 시험공부 하기 싫다~~

문제 해법으로 바로 넘어가자. 

$g, h$가 주어졌을 때 $gk=h^{n}+\alpha$($\alpha<h^{n}$)을 생각해보자.

\[R(h,gk)=R(h,1)=h\]

이때 $k$의 조건이 무엇인지 알아보자. 

\[gk<2h^{n} \Leftrightarrow k<\left[\frac{2h^{n}}{g}\right]\]

그럼 $k$가 자연수가 될 수 있을 정도로 $n$을 적당히 잡고 그 때의 최대의 $k$를 선택하자.

문제에서 요구하는 것은 또 있다. 바로 $\gcd(h,gk)=g$라는 것! 그럼 그냥 $h*=gk$를 하면 된다. 그러고 나면 

\[R(hgk,gk)=R(h,gk)=h\]

짜잔! 아쉽게도 둘의 최대공약수는 $gk$다. 그럼 $hgk+g$로 바꾸면 되겠다. 다시 계산을 해보면

\[R(hgk+g,gk)=R(h,gk)=h\]

이 상황은 $k>1$일 때만 된다. $k=1$인 경우 $g$를 더하지 말자!

문제에서 약간 까다로운 점은 출력하는 값이 $10^{18}$보다 작거나 같아야 한다는 것이다. 이것은 $k$를 구할때 $n$을 적절히 조절하는 방향으로 해결할 수 있다.

 

아래는 정답 코드가 있다. 

# 코드 보기

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)
def r(a,b):
    if b==1:
        return a
    if a>=b:
        return r(a//b,b)
    else:
        return r(b,a)
 
def f(g,h,p):
    a=g
    k=1
    while a>k:
        k*=h
    if p:
        k*=h
    a=(2*k)//a-1
    a*=g
    if a==g:
        g=0
    return (h*a+g,a)
 
t=int(input())
for i in range(t):
    g,h=map(int,input().split())
    ans1=f(g,h,0)
    ans2=f(g,h,1)
    no1=0
    no2=0
    if ans1[0]>10**18:
        no1+=1
    if ans2[0]>10**18:
        no2+=1
 
    if gcd(ans1[0],ans1[1])!=g or r(ans1[0],ans1[1])!=h:
        no1+=1
    if gcd(ans2[0],ans2[1])!=g or r(ans2[0],ans2[1])!=h:
        no2+=1
 
    if no1==0:
        print(ans1[0],ans1[1])
    elif no2==0:
        print(ans2[0],ans2[1])
 

# 닫기