Basically I found three slightly different ways to implement CRT
The first way---- Just classic CRT with help of MODULAR INVERSE using EXTENDED EUCLIDEAN ALGO.
It has time complexity of O(n log lcm(n1,n2,n3,…,nk)) . You can check code here [7k9A0H - Online C++0x Compiler & Debugging Tool - Ideone.com]
Second Way ----Garner’s Algorithm, you can read about it here [Chinese Remainder Theorem - Algorithms for Competitive Programming]
Time Complexity of O(n^2)
Third way ---- This is from one of the Codeforces blog , you can read it here [[Tutorial] Chinese Remainder Theorem - Codeforces]
*Time complexity of O(n log lcm(n1,n2,n3…,nk))
I just want to ask what is the best way out of these three…
I found 1st and 3rd way more intuitive but since CP-ALGORITHMS suggested GARNER’S ALGORITHM then it must have some advantages…
Since I am a beginner, I want to ask from all experienced coders , which approach you all use and WHY ??