首页 > 试题广场 >

公约数

[编程题]公约数

桌面上有 n 张牌，每张牌上写了一个数字，第 i 张牌的数字为 a_i。现在从中选出 K 张牌，把选出牌上的数字全部乘起来，得到一个数 X。

问有多少种不同的选择方案，使得 X 和 A 的最大公约数大于等于 B。

数据范围： $2 \le n \le 50 ，2 \le k \le n , 1 \le B \le A \le 10^5 ， 1 \le a_i \le 10^5 \$ $\$

第一行第 n ， k ， a ，b。接下来一行 n 个数，每张牌上的数字

输出方案数

示例1

输入

5 2 12 6
4 4 1 2 3

算法知识视频讲解

17c89

发表于 2024-02-21 13:12:40

import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner in = new Scanner(System.in); while 展开全文

bandiaoz

发表于 2024-12-29 01:39:24

解题思路这是一个动态规划和数论结合的问题。给定：张牌，每张牌上有一个数字需要选择张牌，将这些数字相乘得到求使得的方案数解决方案：先找出的所有因子使用动态规划，表示选张牌时乘积与的最大公约数为的方案数最后统计所有满足条件（）的方案数关键点：展开全文

基础数学

难度：

6条回答 24收藏 2853浏览

查看代码

公约数

扫一扫，把题目装进口袋