글 읽기 - FAQ 빨리 답나오고 최대공약수 이용해 풀었는데 시간초과가납니다ㅠ(python3)

dlssrb7777 5년 전 0

흠... 시간초과나고 아예 다른방법으로 풀어야되나 생각하다가 혹시라도 조언을 얻을 수 있을까 싶어 질문드립니다!

from sys import stdin
from math import gcd
for i in range(int(stdin.readline())):
    m, n, x, y = map(int, stdin.readline().split())
    g = gcd(m, n)
    mx = set([m * i + x % m for i in range(n // g)])
    ny = set([n * i + y % n for i in range(m // g)])
    if mx & ny:
        if mx & ny == {0}:
            print(m * n // g)
        else:
            print(list(mx & ny).pop())
    else: print(-1)

jh05013 5년 전 1

Python3와 똑같은 문법인데 훨씬 빠른 Pypy3로 제출해 보세요.

dlssrb7777 5년 전 0

@jh05013 통과는 되는데 오래걸리긴 하네요 ㅠㅠ 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

FAQ 빨리 답나오고 최대공약수 이용해 풀었는데 시간초과가납니다ㅠ(python3)

dlssrb7777 5년 전 0

jh05013 5년 전 1

dlssrb7777 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말