서로소 유클리드 호제법 version, https://www.acmicpc.net/problem/9359

baekjoon9359.py

# 값은 잘 나오나, 시간초과가 발생한다. 알아보니 포함-배제의 원리를 사용한다고 한다. 일단 패스

def gcd(m: int, n: int):
    while n != 0:
        t = m % n
        m, n = n, t
    return abs(m)


def f(a: int, b: int, n: int):
    ctn = 0
    for i in range(a, b+1):
        if gcd(n, i) is 1:
            ctn += 1
    return ctn


for i in range(int(input())):
    user = list(map(int, input().split()))
    a, b, n = user[0], user[1], user[2]
    print("Case #" + str(i+1) + ":" + str(f(a, b, n)))