TOYPRO 해설문 - Come(500점)

1. 개요

경기 프로그래밍 사이트 "TOYPRO"의 500점 문제, 제가 Coprime을 설명합니다!
해설을 빠르게 읽고 싶은 사람은 3절부터 읽어주세요.

2. 질문

피비는 두 개의 정수 A와 B를 발견했다.
A곱하기 B회의 수량(A의 B차방)과 B곱하기 A회의 수량(B의 A차방)이 서로 소인지 판정해 주십시오.
서로가 민낯이면'예'를 출력하고, 둘 다 민낯이 아니면'아니오'를 출력하라.
※ 이 질문과 제한에 따라 5초 이내에 실행할 수 있는 프로그램을 만들 수 있습니다.

구속

1\leqq A, B\leqq 10^9

입력 예 1

A = 2
B = 5

출력 예 1

Yes

입력 예 2

A = 10
B = 8

출력 예2

No

3. 해설

3-1.오류 응답 예

우선 간단한 해법으로 A^B, B^A를 실제 계산해 최대 공약수가 1인지 아닌지를 판단하는 방법을 고려할 수 있다.
이때 코드는 다음과 같습니다.

import math

A = 2
B = 5

if math.gcd(pow(A, B), pow(B, A)) == 1:
    print("Yes")
else:
    print("No")

pow(A, B)는 A^B라는 뜻이다.
"뭐야, 이 정도면 해결되는 거 아니야!"그렇게 생각할지도 모르지만, 이 답을 대조해 보면...?

상당히 기다렸지만 끝내지 못했는데..
무슨 일이 있었냐면...

3-2.계산량 정보

실제로 TOYPRO 처리에 5초 이상 시간이 걸리면 그 프로그램은 중단된다.
이 문제의 제약 아래 A, B의 수치는 최대 10^9까지 제시할 수 있음을 알 수 있다.
A^B를 계산하면 그때는 10^9번, 컴퓨터가 1초에 처리할 수 있는 계산 횟수는 10^8번 정도 되기 때문에 5초 이상 걸릴 것으로 예상된다.(2021/04/21:50 수정)
그런 일 없습니다.pow(A, B)의 계산량은 O(logB)이다.(익명 선생님, 지적해 주셔서 감사합니다.)
x를 O(x)로 계산하는 것을 나타낸다.
자세한 내용은 권인 선생의 보도를 보십시오.
로그를 아직 배우지 않은 사람들은'계산의 횟수가 적다'는 것을 인식할 수 있다.(관심이 있으면 꼭 조사해 주세요.)
log10^9번 정도 9번 정도 돼서 괜찮을 것 같아요.
그러나 Pow(A, B)의 값이 매우 커지고 처리가 느려져 실행에 막대한 시간이 걸린다.
(최대 10^{9\times10^9}의 수치입니다.)
이 때문에 위의 그림처럼 정답을 끝낼 수 없는 현상이 나타났다.
그래서 나는 작은 수치로 이 문제를 해결하고 싶다.

3-3.구상의 해답

"A^B와 B^A는 서로 수수한가"로 바꿀 수 있나요?
사실 상호소의 정수로서의 성질은 다음과 같은 몇 가지가 있다.
A, B가 정수이고 n, m이 자연수일 때
만약 A와 B가 서로 수수하다면, A^n과 B^m도 서로 수수하다
또한 반대로 만약에 A^n과 B^m이 서로 소박하다면 A와 B도 서로 소박하다
여기서 이런 성격의 증명을 하는 것은 해설문의 취지에 어긋나기 때문에 생략한다.(왜 이렇게 됐는지 신경 쓰는 사람은'상호간의 본질'을 조사하면 정수적 성질에 관한 기사 몇 개를 발견할 수 있다.)
그렇다면 이상의 상황에 따라 A^B와 B^A는 서로의 소양 여부를 판단하려면 A와 B가 서로 소양을 판정하면 된다.
실시례는 다음과 같다.

import math

A = 2
B = 5

if math.gcd(A, B) == 1:
    print("Yes")
else:
    print("No")

4. 마지막

이 기사를 읽어 주셔서 감사합니다.
글의 오류를 발견하거나 문제가 있다면 해설을 써달라는 질문폐물이 있다면 연락 주시면 좋을 것 같습니다.

사과하다.

이번 기사는 잘못된 정보를 썼다.
미안합니다.
당신이 초기에 지적해 주셔서 대단히 감사합니다.
앞으로 이런 일이 없도록 해설 기사를 더 조심스럽게 쓰겠다.