Java factorization solution O(n + m)
Algorithm:\n1. Create a map  key: (num * num), value: count basing on first array\n2. Go throug the second array, for every number calculate a key containing fa
Algorithm:\n1. Create a map  key: (num * num), value: count basing on first array\n2. Go throug the second array, for every number calculate a key containing factors that are represented odd number of times in number. For example, 60 is 2 * 2 * 3 * 5, the key is "3,5"\n3. Search for the values with the same key processed on previous iterations - they will form squares\n4. Check if the map based on the first array contains corresponding square. Update count if match is found\n5. Store store num under the same key\n\n<pre>\nclass Solution {\n    // Cached factors\n    private final Map&lt;Integer, Map&lt;Integer, Integer&gt;&gt; factorsCache = new HashMap&lt;&gt;();\n\n    /*\n     * Calculates factors for num. Returns a map where\n     * key is prime factor, value is number of times the factor is used.\n     *\n     *  For example, 60 will be represented as\n     * 2 -&gt; 2\n     * 3 -&gt; 1\n     * 5 -&gt; 1\n     */\n    private Map&lt;Integer, Integer&gt; factors(int num) {\n        Map&lt;Integer, Integer&gt; cached = factorsCache.get(num);\n        if (cached != null) {\n            // return cached value (if any)\n            return cached;\n        }\n\n        // handle case num == 1 separately\n        if (num == 1) {\n            Map&lt;Integer, Integer&gt; ret = new HashMap&lt;&gt;();\n            ret.put(1, 1);\n            factorsCache.put(1, ret);\n            return ret;\n        }\n\n        // calculate factors recursively\n        for (int i = 2; i * i &lt;= num; i++) {\n            if (num % i == 0) {\n                Map&lt;Integer, Integer&gt; f1 = factors(i);\n                Map&lt;Integer, Integer&gt; f2 = factors(num / i);\n\n                Map&lt;Integer, Integer&gt; ret = new HashMap&lt;&gt;();\n                for (Map.Entry&lt;Integer, Integer&gt; entry : f1.entrySet()) {\n                    Integer key = entry.getKey();\n                    Integer value = entry.getValue();\n                    ret.put(key, ret.getOrDefault(key, 0) + value);\n                }\n                for (Map.Entry&lt;Integer, Integer&gt; entry : f2.entrySet()) {\n                    Integer key = entry.getKey();\n                    Integer value = entry.getValue();\n                    ret.put(key, ret.getOrDefault(key, 0) + value);\n                }\n\n                factorsCache.put(num, ret);\n                return ret;\n            }\n        }\n\n        // cache the results\n        Map&lt;Integer, Integer&gt; ret = new HashMap&lt;&gt;();\n        ret.put(num, 1);\n        factorsCache.put(num, ret);\n        return ret;\n    }\n\n    public int numTriplets(int[] nums1, int[] nums2) {\n        Map&lt;Long, Integer&gt; squaresMap1 = new HashMap&lt;&gt;();\n        Map&lt;Long, Integer&gt; squaresMap2 = new HashMap&lt;&gt;();\n        for (int n : nums1) {\n            long sq = ((long) n) * n;\n            squaresMap1.put(sq, squaresMap1.getOrDefault(sq, 0) + 1);\n        }\n        for (int n : nums2) {\n            long sq = ((long) n) * n;\n            squaresMap2.put(sq, squaresMap2.getOrDefault(sq, 0) + 1);\n        }\n\n        int ret = 0;\n\n        // check nums1 against squares in nums2\n        ret += count(nums1, squaresMap2);\n\n        // check nums2 against squares in nums1\n        ret += count(nums2, squaresMap1);\n\n        return ret;\n    }\n\n    // cached keys\n    private final Map&lt;Integer, String&gt; keyCache = new HashMap&lt;&gt;();\n\n    /*\n     * Key consists of factors (greater than 1) that are represented odd number of times in num\n     * For example, 60 is 2 * 2 * 3 * 5, the key is "3,5"\n     * 1 -&gt; ""\n     * 2 -&gt; "2"\n     * 3 -&gt; "3"\n     * 4 -&gt; ""\n     * 5 -&gt; "5"\n     * 6 -&gt; "2,3"\n     * ...\n     */\n    private String calculateKey(int num) {\n        String cachedKey = keyCache.get(num);\n        if (cachedKey != null) {\n            return cachedKey;\n        }\n\n        String key = "";\n        if (num &gt; 1) {\n            Map&lt;Integer, Integer&gt; f = factors(num);\n            List&lt;Integer&gt; list = new ArrayList&lt;&gt;();\n            for (Map.Entry&lt;Integer, Integer&gt; entry : f.entrySet()) {\n                if (entry.getValue() % 2 != 0) {\n                    list.add(entry.getKey());\n                }\n            }\n            Collections.sort(list);\n            StringBuilder sb = new StringBuilder();\n            for (int j = 0; j &lt; list.size(); j++) {\n                if (j &gt; 0) {\n                    sb.append(",");\n                }\n                sb.append(list.get(j));\n            }\n            key = sb.toString();\n        }\n\n        keyCache.put(num, key);\n\n        return key;\n    }\n\n\n    private int count(int[] nums, Map&lt;Long, Integer&gt; complementary) {\n        int ret = 0;\n\n        // Examples:\n        // key "3,5" -&gt;\n        //               15 -&gt; 2 (number of times this value was seen previously)\n        //               60 -&gt; 1 (number of times this value was seen previously)\n        // key "3,7" -&gt;\n        //               21 -&gt; 1 (number of times this value was seen previously)\n        //               2100 -&gt; 4 (number of times this value was seen previously)\n        Map&lt;String, Map&lt;Integer, Integer&gt;&gt; previousNumbers = new HashMap&lt;&gt;();\n\n        for (int num : nums) {\n            String key = calculateKey(num);\n\n            // we need to find previously previously seen values with the same key\n            // if current value is 60, the key is "3,5", every value that has the same key will represent a square,\n            // 15, 60, 135 etc.\n            Map&lt;Integer, Integer&gt; counts = previousNumbers.computeIfAbsent(key, k -&gt; new HashMap&lt;&gt;());\n            for (Map.Entry&lt;Integer, Integer&gt; entry : counts.entrySet()) {\n                Integer previous = entry.getKey();\n                long product = previous.longValue() * num;\n\n                // finding a match in the other array\n                Integer complementaryCount = complementary.get(product);\n                if (complementaryCount != null) {\n                    ret += entry.getValue() * complementaryCount;\n                }\n            }\n\n            // recording current number in the map\n            counts.put(num, counts.getOrDefault(num, 0) + 1);\n        }\n\n        return ret;\n    }\n}\n</pre>
[]