#P9640. 补幺梨
补幺梨
补幺梨
题目描述
传说中,早在公元前 年,有个神秘的国家,叫做补幺国。他们当时就已在用一种叫做“补幺梨”的货币,其因形状长得像梨子而得名。
补幺人通过“补幺梨”货币来进行交易。具体地,“补幺梨”有 种面值,分别为 。
补幺人认为,在他们的视野里, 是“补幺梨”基本面值的上限。为了让这些基本面值尽可能均匀地覆盖 ,序列 由输入给出的随机种子 seed 按下面的确定性算法生成。
#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
int n, m;
u32 seed;
int main() {
scanf("%d%d%u", &n, &m, &seed);
mt19937 rng(seed);
auto get = [&]() -> int {
const u32 range = u32(m - 1); // 一共有 m-1 个可能值:2..m
while (true) {
const u64 product = u64(rng()) * u64(range);
const u32 low = u32(product);
if (low < range) {
const u32 threshold = u32(-range) % range;
if (low < threshold) continue;
}
return 2 + int(product >> 32);
}
};
for (int i = 1; i <= n; ++i) {
a[i] = get();
}
}
上述算法只使用标准 mt19937 的 32 位输出,并显式规定了从随机数到 的映射,因此在所有平台上都会得到完全相同的 。
补幺国王拥有每种面值的“补幺梨”无限枚。一个正整数 被称为可以表示,当且仅当存在非负整数 ,使得
。
请你求出最大的、不能被表示的正整数。
输入保证答案存在。
输入格式
第一行输入三个整数 ,分别表示面值种数、面值上限和随机种子。
序列 按题面给出的确定性随机算法生成。
输出格式
输出一个整数,表示最大的不能被表示的正整数。
样例 #1
输入
5 5 3
输出
1
生成的序列为 。
样例 #2
输入
2 100 10
输出
2309
生成的序列为 。
样例 #3
输入
3 100 10
输出
89
生成的序列为 。
样例 #4
输入
50 50000000 97
输出
50823796
数据范围
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,;
- 对于 的数据,,;
- 。