문제가 굉장히 어려워지는 2 가지 포인트가 있어 문의드립니다.
1. n1, n2, n3가 합성수이기 때문에 역원을 구하기 힘들다는점
-> 이는 페르마 소정리가 아닌 확장된 유클리드 호제법을 쓰면 될 것 같긴 하지만 2번의 상황이 문제가 됩니다.
2. n1, n2, n3가 각각 서로소가 아니므로 확장된 유클리드 호제법을 사용하기에도 난감해진다는 점. 이를 해결하려면 n1, n2, n3를 각각 소인수분해하여 사용해야 하는데 이 정도까지 생각하게 되면 코드의 난이도가 상당해질 것으로 예측됩니다.
따라서 이와 같은 방법이 아니더라도 naive하게 푸는 방법 중 시간을 최대한 효율적으로 쓸 수 있는 알고리즘이 있거나 혹은 입력 데이터들의 제한이 있는지 질의드립니다.
