| 题目名称 | 2618. [HZOI 2015]月刊少女驴蛋蛋 |
|---|---|
| 输入输出 | TSUMANNAIKOTO.in/out |
| 难度等级 | ★★★★☆ |
| 时间限制 | 10000 ms (10 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 50 |
| 题目来源 |
 YGOI_真神名曰驴蛋蛋
于2017-02-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：2， 通过率：50% | ||||
 YGOI_真神名曰驴蛋蛋 |
100 | 44.449 s | 0.39 MiB | C++ |
|
YGOI_真神名曰驴蛋蛋 |
0 | 90.000 s | 0.05 MiB | C++ |
| 关于 月刊少女驴蛋蛋 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
数据有问题请找驴蛋蛋
样例有问题请找Knuth 题面有问题请找Keller 题解戳来源 | ||||
|
这题提交一次能卡cogs评测姬将近1分钟呢~
 沉迷学习的假的Keller
2017-02-25 07:42
2楼
| ||||
|
吓得我打开了Ai
 rvalue
2017-02-24 18:45
1楼
| ||||
2618. [HZOI 2015]月刊少女驴蛋蛋
★★★★☆ 输入文件：TSUMANNAIKOTO.in
输出文件：TSUMANNAIKOTO.out
简单对比时间限制：10 s 内存限制：256 MiB
【题目描述】
克里斯共和国有$N$种面值互不相同的货币,其中第$i$种的面值为$a_i$，每种面值各有无限张
现在$驴蛋蛋$要与$Keller$换$C$元零钱,问$Keller$共有多少种方案与$驴蛋蛋$换零钱?
我们约定克里斯共和国有一种面值为$1$的货币,这个面值为$1$的货币将不再给出，也不计入$N$与$a$内，但是仍可使用保证有$a[N]=lcm(a[:])且\frac{N∗a[N]}{gcd(a[:])}≤5000且C≤10^{100}$
其中$a[:]$表示$a$中所有元素
【输入格式】
第一行两个整数$N,Q$
第二行从小到大有$N$个整数描述了$a$
【输出格式】
一个整数,表示Keller与驴蛋蛋换零钱的方案数
【样例输入1】
4 50 5 10 25 50
【样例输出1】
50
【样例输入2】
4 100000000 5 10 25 50
【样例输出2】
66666793333412666685000001
【提示】
对于第$i$个测试点有$log_{10}(C)\le i$
【来源】
