베주의 항등식 - 최대공약수로 만들 수 있는 정수

1. 문제

 

25333번: 개구리 (acmicpc.net)

25333번: 개구리

 

2. 풀이

 

예제를 보면 A,B의 최대공약수의 배수의 개수가 정답일 것 같은데

 

조금 수학적으로 생각해보면

 

A,B로 만들 수 있는 자연수가 X 이내에 몇개나 있느냐?라는 문제와 같은데

 

오른쪽으로 x번 A만큼 점프하면 Ax가 되고 왼쪽으로 y번 B만큼 점프하면 By가 되니까, 만들 수 있는 정수는

 

Ax+By형태와 같다.

 

이는 베주의 항등식 형태와 같으며, 

 

"정수 x,y에 대하여 ax+by의 형태로 표현되는 모든 정수는 gcd(a,b)의 배수와 같다"

 

귀찮아서 증명하진 않았네..?

 

https://deepdata.tistory.com/577

모듈로 연산에서 나눗셈을 하는 방법(모듈로 곱셈의 역원 구하기)

 

베주 항등식 - 나무위키 (namu.wiki)

 

 

따라서, a,b의 최대공약수를 구하고 x 이내에 최대공약수의 배수가 몇개나 있는지 구하면 된다.

 

1부터 x까지 c의 배수의 개수는 x//c라는건 알고 있겠지..?

 

from sys import stdin

def gcd(a,b):
    
    while b != 0:
        
        a,b = b,a%b
    
    return a

T = int(stdin.readline())

for _ in range(T):
    
    a,b,x = map(int,stdin.readline().split())

    gcd_ab = gcd(a,b)

    print(x//gcd_ab)