C++  unordered_map dp vs dp+ binary search||Beats 96.85%
Intuition\n Describe your first thoughts on how to solve this problem. \nLet $mp[x]$ denote the number of binary trees with root->val=x.\nUse dynamic programmin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet $mp[x]$ denote the number of binary trees with `root->val=x`.\nUse dynamic programming with hash table. Use the formula\n$$\nans=\\sum_x mp[x]\n$$\nwhere $mp[x]=\\sum_{d|x}mp[x/d]\\times mp[d]$  where $d$ is a divisor of $x$\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFor fast algorithm (reducing $O(n)$ to $O(\\sqrt{n})$ for the inner loop) the formula above can be rewritten as follows\n$$\nmp[x]=\\sum_{d|x & d\\leq \\sqrt{x}}c \\times mp[x/d]\\times mp[d]\n$$\nwhere $c=1$ if $x/d=d$ otherwise $c=2$.\n\nThe hash table `mp`is suggested to use `unordered_map`, if `map` is applied the running time will be doubled.\n\n\n2nd approach uses also DP, but without hash table, insteadly uses binary search! That is not slow with running time 18 ms & beats 96.06%.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n\\sqrt{n})$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n# Code 34ms Beats 91.34%-> 15 ms Beats 96.85%\n```\nclass Solution {\npublic:\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        const int mod =1e9+7;\n        sort(arr.begin(), arr.end());\n        unordered_map<int, long long> mp;\n        long long ans = 0;\n\n        for (int x: arr) {\n            mp[x]=1;\n            int sqrt_x=sqrt(x);\n\n            #pragma unroll\n            for (int j=0;  arr[j]<=sqrt_x; j++){\n                int y=arr[j];\n                if (x % y == 0){\n                    int z=x/y;\n                    int c=(y==z)?1:2;\n                    if (mp.count(z))// Add this faster\n                        mp[x]=(mp[x]+mp[y]*mp[z]*c)%mod;\n                }\n                   \n            }\n                \n            ans = (ans + mp[x]) % mod;\n        }\n        return ans;\n    }\n};\n```\n# Code using DP+ binary search runs in 18 ms & Beats 96.06%\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:\n    const int mod=1e9+7;\n    int numFactoredBinaryTrees(vector<int>& arr) {\n        int n=arr.size();\n        sort(arr.begin(), arr.end());\n        vector<pair<int, long long>> A(n);\n        long long ans=0;\n        for(int i=0; i<n; i++){\n            int x=arr[i];\n            A[i]={x, 1};\n            int sqrt_x=sqrt(x);\n\n            #pragma unroll\n            for(int j=0; A[j].first<=sqrt_x; j++){\n                auto& [y, count]=A[j];\n                if (x%y == 0){\n                    int z=x/y;\n                    if (z==y){\n                        A[i].second=(A[i].second+count*count)% mod;\n                    }\n                    else{\n                        int idx=lower_bound(arr.begin()+j, arr.end(), z)    \n                        -arr.begin();\n                        if (idx<n && arr[idx]==z)\n                            A[i].second=(A[i].second+count*A[idx].second*2)% mod;\n                    }\n\n                }\n            }\n            ans =(ans+ A[i].second)%mod;\n        }\n        return ans;\n    }\n};\n```
['Hash Table', 'Binary Search', 'Dynamic Programming', 'C++']