一个长度为n的序列,从这个序列中删除一些数,使得剩下的元素的最大公约数恰好等于k的C++代码
时间: 2023-05-29 16:07:22 浏览: 114
以下是使用动态规划的方法求解。
首先可以将序列中的数按照从小到大的顺序排序,记为a[1], a[2], ..., a[n]。
设dp[i][j]表示考虑前i个数,最大公约数为j的方案数,那么状态转移方程为:
dp[i][j] = dp[i-1][j] + dp[i-1][gcd(j, a[i])]
其中gcd(j, a[i])表示j和a[i]的最大公约数,也就是新的最大公约数。
最终答案为dp[n][k]。
代码如下:
```
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1005;
int a[MAXN];
int dp[MAXN][MAXN];
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
memset(dp, 0, sizeof(dp));
// 初始化
for (int i = 1; i <= n; i++) {
dp[i][a[i]] = 1;
}
// dp转移
for (int i = 2; i <= n; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j] = dp[i-1][j] + dp[i-1][gcd(j, a[i])];
}
}
cout << dp[n][k] << endl;
return 0;
}
```