Solve it in two parts
Our answer will arrive by addition from two parts\n\n1. when one number is direct multiple of K then it will form pair with every other number in the array ie a
Our answer will arrive by addition from two parts\n\n1. when one number is direct multiple of K then it will form pair with every other number in the array ie ans += N - 1.\nIn the end we subtract mC2 where m is total direct divisible so as to cancel out repeated ones\n\n2. we created another array where number which aren\'t directly divisible by K are present. We assume k will arrive via n1 * n2.\nn1 arrives from current element i.e v[i] and n2 from all other elements hence we remove gcd(v[i],k) from k.  **g = k / gcd(v[i],k)**\nAlso maintain a map to store all factors as we travel the array for n2.\n \n ```long long ans = 0;\n        int n = a.size();\n        long long int count = 0;\n        vector<int> v;\n        \n        // Part 1 \n        for ( int i = 0; i < n; i++ )\n        {\n            if ( a[i]%k == 0 )\n            {\n                ans += (n-1);\n                count++;\n            }\n            else if ( __gcd(a[i],k) != 1 )\n                v.push_back(a[i]);\n        }\n        ans -= (count*(count-1))/2;\n        \n        \n        // Part 2\n        unordered_map<int,int> mp;\n        for ( int i = 0 ; i < v.size() ; i++ )\n        {\n            int g = k / __gcd(v[i],k);\n            ans += mp[g];\n            for ( int j = 1 ; j <= sqrt(v[i]) ; j++ )\n            {\n                if ( v[i] % j == 0 )\n                {\n                    mp[j]++;\n                    if ( v[i] / j != j )\n                        mp[v[i]/j]++;\n                }\n            }\n        }\n        \n        return ans;
[]