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 ??