题解 | #公约数#

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

// 计算最大公约数
int gcd(int x, int y) {
    while(y != 0) {
        int t = x % y;
        x = y;
        y = t;
    }
    return x;
}

int main() {
    int n, K, A, B;
    scanf("%d%d%d%d", &n, &K, &A, &B);
    
    // 读入牌面数字
    long a[n];
    for(int i = 0; i < n; i++)
        scanf("%ld", &a[i]);
    
    // 预处理A的所有因子
    vector<int> factors;
    for(int i = 1; i * i <= A; i++) {
        if(A % i == 0) {
            factors.push_back(i);
            if(A/i != i)
                factors.push_back(A/i);
        }
    }
    sort(factors.begin(), factors.end());
    
    // dp[i][j]表示选j张牌时乘积与A的最大公约数为i的方案数
    long dp[100010][51] = {0};
    
    // 动态规划过程
    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: factors)
                dp[gcd(a[i]*x, A)][j] += dp[x][j-1];
        }
    
    // 统计满足条件的方案数
    long result = 0;
    for(int i = B; i <= A; i++)
        result += dp[i][K];
    
    printf("%ld\n", result);
    return 0;
}

import java.util.*;

public class Main {
    // 计算最大公约数
    static int gcd(int x, int y) {
        while(y != 0) {
            int t = x % y;
            x = y;
            y = t;
        }
        return x;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int K = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        
        // 读入牌面数字
        long[] a = new long[n];
        for(int i = 0; i < n; i++)
            a[i] = sc.nextLong();
        
        // 预处理A的所有因子
        List<Integer> factors = new ArrayList<>();
        for(int i = 1; i * i <= A; i++) {
            if(A % i == 0) {
                factors.add(i);
                if(A/i != i)
                    factors.add(A/i);
            }
        }
        Collections.sort(factors);
        
        // dp[i][j]表示选j张牌时乘积与A的最大公约数为i的方案数
        long[][] dp = new long[100010][51];
        
        // 动态规划过程
        for(int i = 0; i < n; i++)
            for(int j = K; j > 0; j--) {
                if(j == 1) {
                    dp[gcd((int)a[i], A)][j] += 1;
                    break;
                }
                for(int x: factors)
                    dp[gcd((int)(a[i]*x), A)][j] += dp[x][j-1];
            }
        
        // 统计满足条件的方案数
        long result = 0;
        for(int i = B; i <= A; i++)
            result += dp[i][K];
        
        System.out.println(result);
    }
}

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def solve():
    n, K, A, B = map(int, input().split())
    a = list(map(int, input().split()))
    
    # 预处理A的所有因子
    factors = []
    i = 1
    while i * i <= A:
        if A % i == 0:
            factors.append(i)
            if A//i != i:
                factors.append(A//i)
        i += 1
    factors.sort()
    
    # dp[i][j]表示选j张牌时乘积与A的最大公约数为i的方案数
    dp = [[0] * (n+1) for _ in range(100010)]
    
    # 动态规划过程
    for i in range(n):
        for j in range(K, 0, -1):
            if j == 1:
                dp[gcd(a[i], A)][j] += 1
                break
            for x in factors:
                dp[gcd(a[i]*x, A)][j] += dp[x][j-1]
    
    # 统计满足条件的方案数
    result = sum(dp[i][K] for i in range(B, A+1))
    print(result)

solve()