[C++]  Factorization + Factor tree + Prefix Sum
Factorization + Prefix Sum\n\nImitating the suffix automaton, we construct a factor tree:\n\n1. Preprocess and factorize the numbers in the interval [1, 50000].
Factorization + Prefix Sum\n\nImitating the suffix automaton, we construct a factor tree:\n\n1. Preprocess and factorize the numbers in the interval [1, 50000].\n2. Traverse the array from left to right, and record the count of elements that have factor w as cnt[w]. (for the first i elements, how many have factor w)\n\nFor element ai, traverse its factors from largest to smallest, and consider this factor as the greatest common divisor (GCD) of element ai and the previous elements.\n\nAssume that element ai has factors u, v, where u = k * v:\n1. Consider factor u . cnt[u] represents the number of elements among the previous ones that have factor u. The number of pairs where u is the GCD is cnt[u].\n2. After processing factor u, you also need to process the factors of u. Since if two elements share a common divisor u, the factors of u must also be their common divisors, so cnt[v] needs to subtract cnt[u].\n\n**code:**\n```\ntypedef long long       ll;\nconst int               N = 10 + 1e5;\n\nconst int           T = 5e4;\nvector<set<int>>    f;\n\nint init_fun = []() -> int {\n    f.assign(T+10, {});\n    for (int i = 1; i <= T; i++) {\n        for (int k = 1; k*k <= i; k++) if (i%k == 0) f[i].insert(k), f[i].insert(i/k);\n    }\n    return 1;\n}();\n\n\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) { \n\n        ll  sum[N];     memset(sum, 0, sizeof(sum));\n        ll  cnt[N];     memset(cnt, 0, sizeof(cnt));\n        ll  add[N];     memset(add, 0, sizeof(add));\n\n        for (auto s : nums) {\n            for (auto u : f[s]) add[u] = cnt[u];\n            for (auto p = f[s].rbegin(); p != f[s].rend(); p++) {               int u = *p;\n                for (auto v : f[u]) if (v != u && add[v]) add[v] -= add[u];\n            }\n            for (auto u : f[s]) sum[u] += add[u], cnt[u]++, add[u] = 0;\n        }\n\n\n        ll  upp = *max_element(nums.begin(), nums.end());\n        for (int i = 1; i <= upp; i++) sum[i] += sum[i-1];\n\n\n        vector<int> ans;\n        for (auto pos : queries) ans.push_back(lower_bound(sum+1, sum+upp+1, pos+1) - sum);\n        return ans;\n    }\n};\n\n```\n\n\n\n**Code Optimization:**\n\nAfter reviewing other people\'s solutions, I found that their approach is fundamentally similar to mine but more concise: \n* \tit is based on a global consideration of the factor tree, counting the occurrences of each factor and directly calculating the results.\n\n```\ntypedef long long       ll;\n\nclass Solution {\npublic:\n    vector<int> gcdValues(vector<int>& nums, vector<long long>& queries) { \n        int n = *max_element(nums.begin(), nums.end());\n\n        // Preprocessing 1:     Count how many times each factor appears.\n        ll  cnt[n+10];  memset(cnt, 0, sizeof(cnt));\n        for (auto i : nums) {\n            for (int k = 1; k*k <= i; k++) if (i%k == 0) {\n                cnt[k]++;\n                if (k*k != i) cnt[i/k]++;\n            }\n        }\n\n        // Enumerate GCD:       Enumerate factors from large to small, considering each factor as the greatest common divisor\n        ll  f[n+10];    memset(f, 0, sizeof(f));\n        for (int i = n; i >= 1; i--) {      f[i] = cnt[i] * (cnt[i] - 1) / 2;\n            for (int k = 2*i; k <= n; k+=i) f[i] -= f[k];\n        } \n\n        // Prefix Sum\n        ll  sum[n+10];  memset(sum, 0, sizeof(sum));\n        for (int i = 1; i <= n; i++) sum[i] = sum[i-1] + f[i];\n\n\n        vector<int> ans;\n        for (auto k : queries) ans.push_back(lower_bound(sum+1, sum+n+1, k+1) - sum); \n        return ans;\n    }\n};\n\n```\n\n\n
[]