Computing divisors (maths solution)
Intuition\n Describe your first thoughts on how to solve this problem. \nLet\'s find all divisors of an integer!\n\n# Approach\n Describe your approach to solvi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet\'s find all divisors of an integer!\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIf `nums1[i]` is divisible by `k`, you need to find all divisors of `nums1[i]` in `nums2`.\n\n# Complexity\n- Time complexity: $$(1 + x) \\cdot O(n) + O(m)$$, where $$x$$ is the sum of the unique integers in the array $$nums1$$ or `x = sum(set(nums1))`.\n- * It could be optimised if you\'re looking for divisors up to the square root of an integer.\n- * In the worst case, for $$nums1 = [1, 2, ..., 49, 50]$$, it\'s $$\\frac{50 \\cdot 51}{2} + 100=1375$$ operations.\n- * Due to constrains, $$1 <= n, m <= 50$$, it\'s around $$O(n \\cdot m) = 50 \\cdot 50 = 2500$$ operations.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n) + O(m)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n---\n* You could find some other extraordinary solutions in my [profile](https://leetcode.com/almostmonday/) on the Solutions tab (I don\'t post obvious or not interesting solutions at all.)\n* If this was helpful, please upvote so that others can see this solution too.\n---\n\n\n# Code\n```\nclass Solution:\n    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:\n        d, res = Counter(nums2), 0\n        for x, cnt in Counter(nums1).items():\n           if x % k == 0:\n            x //= k\n            for m in range(1, x + 1):\n                if not x % m and m in d: res += d[m] * cnt\n\n        return res\n```
['Math', 'Number Theory', 'Python', 'Python3']