How gcd(a,k) * gcd(b,k) % k == 0 ? || Explained with example
Intuition\nLet\'s first understand this property:\n\nIf (ab)%k==0, then\ngcd(a,k) * gcd(b,k) % k is also 0\n\nLet\u2019s assume two numbers 504 and 819. Their p
## Intuition\nLet\'s first understand this property:\n\n<b>If (a*b)%k==0, then\ngcd(a,k) * gcd(b,k) % k is also 0</b>\n\nLet\u2019s assume two numbers 504 and 819. Their prime factorization can be written as:\n\n504 = (2^3) * (3^2) * 7\n819 = (3^2) * 7 * 13\n\nNow gcd(504,819) = 63 and 63 = (3^2) * 7\n\n<b>gcd(a,b) is the multiplication of common prime factors of a and b.</b>\n\nComing back to the statement\nHow gcd(a,k) * gcd(b,k) % k is 0 ?\n\nFor any number to be divisble by k it need to have atleast all the prime factors of k.\n\ngcd(a,k) = Multiplication of all prime factors of k available in a.\nand\ngcd(b,k) = Multiplication of all prime factors of k available in b.\n\nIf gcd(a,k) * gcd(b,k) % k is 0, it means some of the prime factors of k are contributed by a and some of the prime factors of k are contributed by b and thier multiplication has all the prime factors of k which means a*b is divisble by k.\n\nWe dont care about prime factors of a or b which are not prime factors of k because they will not help us in making a*b divisible by k.\n\nExample:\n\nLet k=84, a=24, b=273\n\nk = 84 = (2^2) * 3 * 7\na = 24 = (2^3) * 3\nb = 273 =  3 * 7 * 13\n\ngcd(a,k) = (2^2) * 3 (Common prime factors of a and k)\ngcd(b,k) = 7 * 3 (Common prime factors of b and k)\n\ngcd(a,k) * gcd(b,k) = (2^2) * (3^2) * 7\nwhich has all prime factors of k thus a*b is divisble by k.\n\n## Now the solution:\n\nAs compared to checking for every pair, if we check for gcd of every number with k then the operations will be less because the number of prime factors of a number will be less.\n\nCode:\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\n## Time Complexity - O(N*sqrt(K))\n\nWhy sqrt(K):\nSince we are taking gcd, it means we are considering factors of K and the number of factors of K will not be above 2*sqrt(K).\n\nI hope you got the logic.\n\nYou can ask your questions in comment section.\n\nPlease upvote if you found this helpful.
['Math', 'C']