公约数

#include <bits/stdc++.h>
using namespace std;

int gcd(int x, int y){
    int t = x%y;
    while(t != 0){
        x = y;
        y = t;
        t = x%y;
    }
    return y;
}

int main(){
    int n, K, A, B;
    scanf("%d%d%d%d", &n, &K, &A, &B);
    long a[n], dp[100001][n+1]={0};
    for(int i=0;i<n;i++)
        scanf("%ld", &a[i]);
    vector<int> v;
    for(int i=1;i*i<=A;i++){
        if(A%i==0){
            v.push_back(i);
            if(A/i != i)
                v.push_back(A/i);
        }
    }
    sort(v.begin(), v.end());
    for(int i=0;i<n;i++)
        for(int j=K;j>0;j--){
            if(j==1){
                dp[gcd(a[i], A)][j] += 1;
                break;
            }
            for(auto &x: v)
                dp[gcd(a[i]*x, A)][j] += dp[x][j-1]; 
        }
    long s = 0;
    for(int i=B;i<=A;i++)
        s += dp[i][K];
    printf("%ld\n", s);
    return 0;
}

思路：d[i][j][k]表示前i个数选j个数的乘积与A的GCD为k的方案数。
如果k达到100000，会MLE。怎么办呢？
由于A的因子个数最多也就100多个，所以A的GCD也就100多个。那么只要枚举A的因子数即可。

#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+10;
typedef long long ll;
ll d[2][51][10001];
int st[MAX];
vector<int>v;
ll ***(ll x,ll y){return y==0?x:***(y,x%y);}
int main()
{
    int n,m,A,B;
    cin>>n>>m>>A>>B;
    for(int i=1;i*i<=A;i++)
    {
        if(A%i==0)
        {
            v.push_back(i);
            if(A/i!=i)v.push_back(A/i);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++)st[v[i]]=i;
    memset(d,0,sizeof d);
    for(int i=1;i<=n;i++)
    {
        ll x;
        scanf("%lld",&x);
        d[i&1][1][st[***(x,A)]]=1;
        for(int j=1;j<=m;j++)
        {
            for(int k=0;k<v.size();k++)
            {
                if(d[(i&1)^1][j][k]==0)continue;
                if(j<m)
                {
                    if(***(A,v[k]*x)<=B)d[i&1][j+1][st[***(A,v[k]*x)]]+=d[(i&1)^1][j][k];
                    else d[i&1][j+1][st[A]]+=d[(i&1)^1][j][k];
                }
                d[i&1][j][k]+=d[(i&1)^1][j][k];
            }
        }
        memset(d[(i&1)^1],0,sizeof d[(i&1)^1]);
    }
    ll ans=0;
    for(int i=0;i<v.size();i++)
    {
        if(v[i]>=B)ans+=d[n&1][m][i];
    }
    printf("%lld\n",ans);
    return 0;
}

#include <cstring>
#include <map>
#include <vector>

using namespace std;

class node{
public:
    long long num, mygcd;
public:
    bool operator<(const node &newnode) const   
    {
        if (num < newnode.num) {
            return true;
        } else if (num == newnode.num) {
            if ( mygcd < newnode.mygcd ) {
                return true;
            }
        } 
        return false;
    }
    
    node(long long num, long long mygcd){
        this->num = num;
        this->mygcd = mygcd;
    }
            
};

vector<node> v;
vector<long long> vnum;
map<node, long long> mymap;
map<node, long long>::iterator it;

long long gcd(long long x, long long y){
    if (x > y) return gcd(y,x);
    if (y % x == 0) return x;
    return gcd(y%x, x);
}

int main(){
    long long a[50], n, K, A, B;
    cin >> n >> K >> A >> B;
    for (int i=0; i<n; ++i)
        cin >> a[i];
    
    mymap.clear();
    node p(0,1);
    mymap[p] = 1;
    for (int i=0; i<n; ++i){
        v.clear();
        vnum.clear();
        for (it = mymap.begin(); it != mymap.end(); it++){
            p = it->first;
            if (p.num == K) continue;
            p.num += 1;
            p.mygcd = gcd(p.mygcd * a[i], A);
            v.push_back(p);
            vnum.push_back(it->second);
        }
        for (int j=0; j<v.size(); ++j){
            p = v[j];
            if (mymap.find(p) == mymap.end())
                mymap[p] = vnum[j];
            else
                mymap[p] += vnum[j];
        }
    }
    
    long long ans = 0;
    for (it = mymap.begin(); it != mymap.end(); it++){
        p = it->first;
        if (p.num == K && p.mygcd >= B) ans += it->second;
    }
    
    cout << ans;
    
} 

//考虑递归+回溯取长度为k的所有组合
//考虑求当前组合的乘积对于A,B的最大公约数情况(直接循环相减至两个数相等)
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution{
public:
    vector<vector<int>> AllCombinations(vector<int>& vec,int K){
        sort(vec.begin(),vec.end()); //重复元素，别忘记先sort+set限定唯一性//不需要set限定！！！
        dfs(vec,K,0);
        return res;
    }
private:
    vector<vector<int>> res;
    vector<int> tmp;
    //set<vector<int>> S; //限定唯一性，一开始考虑错了，所以死活只有2，以为样例错了，在这里不需要唯一性
    
    void dfs(vector<int>& vec,int K,int idx){
        if((int)tmp.size()==K){
            res.push_back(tmp);
            return;
        }
        for(int i=idx;i<(int)vec.size();++i){
            tmp.push_back(vec[i]);
            dfs(vec,K,i+1);
            tmp.pop_back();
        }
    }
};
bool judge(vector<int>& nums,int A,int B){
    long long X=1;
    for(auto num:nums)
        X*=num;
    //判定X和A的最大公约数
    int target;
    if(X==A)
        target=X;
    else{
        while(1){
            if(X<A)
                A-=X;
            else if(X>A)
                X-=A;
            else{
                target=X;
                break;
            }
        }
    }
    return target>=B;
}
int main(){
    int n,K,A,B;
    cin>>n>>K>>A>>B;
    int idx=0;
    vector<int> vec(n);
    while(n--)
        cin>>vec[idx++];
    //递归+回溯取所有可能
    Solution sol;
    vector<vector<int>> res=sol.AllCombinations(vec,K);
    int cnt=0; //最终组合数目
    for(int i=0;i<res.size();++i){
        vector<int> cur=res[i]; //判定最大公约数
        if(judge(cur,A,B))
            cnt++;
    }
    cout<<cnt;
    return 0;
}

这是原来想的，给定的样例是过了，但是数据量大的时候超时错误，需要优化一下