题目链接：这里 题意：给你n个数，问你里面有多少个集合的gcd为x。最多有10000个不同的数。 解法：dp[i]代表有多少个集合的gcd为i，我们直接DP的话，复杂度高达10000*100000 显然T的对吧。但是发现题目里面给的数字最多10000个不同的数，所以我们先离散化之后再DP，复杂度可以降低为1e8就可以通过了。
//hackerrank Xtreme8.0 - Play with GCD //dp[i]代表有多少个集合的gcd为i #include <bits/stdc++.h> using namespace std; const int maxn = 100005; const int mod = 1e9+7; int n, a[maxn], p[maxn], dp[10005]; long long mi[maxn]; vector <int> V; map <int, int> H; void add(int &x, int y) { x += y; if(x >= mod) x %= mod; } int main() { memset(dp, 0, sizeof(dp)); scanf("%d", &n); mi[0] = 1LL; for(int i = 1; i <= n; i++) { mi[i] = mi[i-1] * 2LL % mod; } for(int i = 1; i <= n; i++) { scanf("%d", &p[i]); V.push_back(p[i]); } sort(V.begin(), V.end()), V.erase(unique(V.begin(), V.end()), V.end()); for(int i = 0; i < (int)V.size(); i++) H[V[i]] = i; for(int i = 1; i <= n; i++) a[H[p[i]]]++; for(int i = 0; i < (int)V.size(); i++) { for(int j = 1; j <= 10000; j++) { add(dp[__gcd(j, V[i])], 1LL*(mi[a[i]]-1)*dp[j]%mod); } add(dp[V[i]], mi[a[i]] - 1); } int q, x; scanf("%d", &q); while(q--) { scanf("%d", &x); printf("%d\n", dp[x]); } return 0; }