2번 gcd는 재귀 함수로 구현되어 있군요.

파이썬에서는 재귀 함수 호출의 횟수를 기본적으로 제한해 놓았기 때문에 재귀 함수가 너무 깊어지면 에러로 처리됩니다.

이 문제의 테스트 케이스 중에 제한된 깊이를 넘어서 재귀 함수를 호출하게 만드는 테스트 케이스가 있나 보네요.

반대로 이런 테스트 케이스가 없는 문제에서는 코드가 정상적으로 작동하겠죠? 아마도 1934번과 13241번 문제가 이 경우인 것 같습니다.

sys.setrecursionlimit(n)을 이용하면 재귀 함수 호출 제한을 n회로 설정할 수 있습니다.

문제의 조건을 잘 확인하시고 제한을 여유롭게 설정하시면 코드가 정상적으로 작동할 것 같네요.

더 자세한 내용은 인터넷에서 "파이썬 재귀 제한"에 대한 내용을 찾아보시는 것을 추천해드립니다.

2번 함수에서 A mod B != 0일때 (32번 줄)이 잘못 작성되었습니다. return gcd(b, a%b)로 바꿔보세요.

Python은 디폴트로 recursion depth를 1000으로 가지고 있습니다. GCD 함수는 log N에 작동함으로 제한된 깊이를 넘어 갈 일은 없습니다.

아... 그러네요. 디버그 한번 돌려볼걸 그랬습니다
두분 다 감사합니다. 재귀 제한도 알아볼게요