174 ms faster then 94.89%[c++] with explanation( O(N+K) time complexity??)
The idea behind using gcd is that (n1 * n2 % k == 0) is the same as (gcd(n1,k) * gcd(n2,k)) % k == 0\nThis allows us to compare only the gcd\'s to each other in
The idea behind using gcd is that ```(n1 * n2 % k == 0)``` is the same as ```(gcd(n1,k) * gcd(n2,k)) % k == 0```\nThis allows us to compare only the gcd\'s to each other instead of comparing all the numbers.\n\nI read in a [post](https://leetcode.com/problems/count-array-pairs-divisible-by-k/discuss/1785906/How-gcd(ak)-*-gcd(bk)-k-0-oror-Explained-with-example) that **the amount of gcd\'s is atleast limited to 2*sqrt(k)**. For [k<=100k] this would mean a max of 625 gcd\'s . However when testing I got 96 gcd\'s max, but I might have missed some. There also cannot be more gcd\'s then there are numbers. This means there is a great speed increase compared to comparing all numbers against each other.\n\nFor a explanation on why ```(n1 * n2 % k == 0)``` is the same as ```(gcd(n1,k) * gcd(n2,k)) % k == 0``` see the [post](https://leetcode.com/problems/count-array-pairs-divisible-by-k/discuss/1785906/How-gcd(ak)-*-gcd(bk)-k-0-oror-Explained-with-example).\n\nAllot of people choose to keep a list of gcd\'s together with a count of those gcd\'s. I see nothing wrong with this. But then they compare to this list for each number in nums. I think it would be faster to just compare the gcd\'s against each other in a seperate loop. (note I do know allot of people did this already but non of those posts apear in Most votes). [An example of comparing against gcd\'s for each number by rupak:](https://leetcode.com/problems/count-array-pairs-divisible-by-k/discuss/1785906/How-gcd(ak)-*-gcd(bk)-k-0-oror-Explained-with-example)\n```\ntypedef long long ll;\n\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        unordered_map<ll, ll> gcdCount;\n        ll ans = 0;\n        for (ll i = 0; i < nums.size(); ++i)\n        {\n            ll currgcd = __gcd(nums[i], k);\n            for (auto &[gc_d, count] : gcdCount)\n                if ((currgcd * gc_d) % k == 0)\n                    ans += count;\n            gcdCount[currgcd]++;\n        }\n        return ans;\n    }\n};\n```\n\nHe says that this has a time complexity of  **O(N*sqrt(K))**. \n\nInstead comparing gcd\'s in a seperate loop would change the N into sqrt(K) here. However you still need to itterate over N so I would belief that this would cause the time complexity to be O(sqrt(K)*sqrt(K) + N) = **O(K+N)**.  (I have not been educated on this stuff and my measured time does not show such a great speedUp, so please correct me if I am wrong)\n\n\n### **Implimentation**:\nFirst I go over all numbers and determine the gcd(num,k) off all values:\n```\nstd::unordered_map<int/*gcd*/,int /*count*/> gcds;//count of gcds for each num\nfor(const int& num:nums){//for each num \n\t gcds[__gcd(num, k)]++;//calculate the gcd and increase its count in gcds map\n}\n```\nWhen a gcd pair is valid, the count of those gcd\'s can be used to calculate the combinations of numbers that are valid.\nwhen gcd1 != gcd2 the count increase simply equals ```count1*count2```. When gcd1 == gcd2 the count increase is ```(count1 * (count1 - 1))/2```\n\nUsing this I can compare each gcd to all other gcd\'s and itself. \n```\n//look for matches of gcd that indicate a valid pair. for this I used gcd2 % (k/gcd1) == 0\nfor(auto it1 = gcds.begin(); it1 != gcds.cend();it1++){\n\tconst int kDivGcd1 = k/(it1->first);// k/gcd1\n\t\n\t//For all gcds that come after this one (and this one aswell) in the list of gcds.\n\tfor(auto it2 = it1; it2 != gcds.cend(); it2++){\n\t\tif((it2->first % kDivGcd1) == 0){//if match [gcd2 % kDivGcd1 == 0]\n\t\t\tif(it1 == it2)   //if gcd1 == gcd2\n\t\t\t\trCount += ((long long)it1->second * (long long)(it2->second-1))/2; //rCount += (count * (count-1))/2\n\t\t\telse //if gcd1 != gcd2\n\t\t\t\trCount += (long long)it1->second * (long long)(it2->second); //rCount += count1*count2\n\t\t}\n\t}\n}\n```\nnote: ```((gcd1 * gcd2) % k == 0)``` was changed into: ```gcd2 % (k/gcd1) == 0```. This works because k%gcd1 == 0. This usefull because it allows us to calculate k/gcd1 just one time. \n\n\nAdding this to the the prev-code:\n```\nlong long countPairs(vector<int>& nums, int k) {\n        std::unordered_map<int/*gcd*/,int /*count*/> gcds;//count of gcds for each num\n        long long rCount = 0;\n        \n        for(const int& num:nums){\n            gcds[__gcd(num, k)]++;//calculate the gcd and increase its count in gcds map\n        }\n        \n        //look for matches of gcd that indicate a valid pair. for this I used gcd2 % (k/gcd1) == 0\n        for(auto it1 = gcds.begin(); it1 != gcds.cend();it1++){\n            const int kDivGcd1 = k/(it1->first);// k/gcd1\n\t\t\t//For all gcds that come after this one (and this one aswell) in the list of gcds\n            for(auto it2 = it1; it2 != gcds.cend(); it2++){\n                if((it2->first % kDivGcd1) == 0){//if match [gcd2 % kDivGcd1 == 0]\n                    if(it1 == it2)\n                        rCount += ((long long)it1->second * (long long)(it2->second-1))/2; //rCount += (count * (count-1))/2\n                    else\n                        rCount += (long long)it1->second * (long long)(it2->second); //rCount += count1*count2\n                }\n            }\n\n        }\n        \n        return rCount;\n    }\n```\nor if you hate comments:\n```\nclass Solution {\npublic:\n    long long countPairs(vector<int>& nums, int k) {\n        std::unordered_map<int/*gcd*/,int /*count*/> gcds;\n        long long rCount = 0;\n        for(const int& num:nums) gcds[__gcd(num, k)]++;\n        \n        for(auto it1 = gcds.begin(); it1 != gcds.cend();it1++){\n            const int kDivGcd1 = k/(it1->first);\n            for(auto it2 = it1; it2 != gcds.cend(); it2++){\n                if((it2->first % kDivGcd1) == 0){\n                    if(it1 == it2)rCount += ((long long)it1->second * (long long)(it2->second-1))/2;\n                    else rCount += (long long)it1->second * (long long)(it2->second); \n                }\n            }\n        }\n        return rCount;\n    }\n};\n```
['C']