#P9640. 补幺梨

    ID: 6256 传统题 3000ms 512MiB 尝试: 4 已通过: 1 难度: 6 上传者: 标签>图论最短路数论动态规划CF1900模运算背包 DP

补幺梨

补幺梨

题目描述

传说中,早在公元前 114514114514 年,有个神秘的国家,叫做补幺国。他们当时就已在用一种叫做“补幺梨”的货币,其因形状长得像梨子而得名。

补幺人通过“补幺梨”货币来进行交易。具体地,“补幺梨”有 nn 种面值,分别为 a1,a2,…,ana_1,a_2,\dots,a_n。

补幺人认为,在他们的视野里,mm 是“补幺梨”基本面值的上限。为了让这些基本面值尽可能均匀地覆盖 [2,m][2,m],序列 aa 由输入给出的随机种子 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 位输出,并显式规定了从随机数到 [2,m][2,m] 的映射,因此在所有平台上都会得到完全相同的 aa。

补幺国王拥有每种面值的“补幺梨”无限枚。一个正整数 xx 被称为可以表示,当且仅当存在非负整数 c1,c2,…,cnc_1,c_2,\dots,c_n,使得

x=c1a1+c2a2+⋯+cnanx=c_1a_1+c_2a_2+\cdots+c_na_n。

请你求出最大的、不能被表示的正整数。

输入保证答案存在。

输入格式

第一行输入三个整数 n,m,seedn,m,seed,分别表示面值种数、面值上限和随机种子。

序列 a1,a2,…,ana_1,a_2,\dots,a_n 按题面给出的确定性随机算法生成。

输出格式

输出一个整数,表示最大的不能被表示的正整数。

样例 #1

输入

5 5 3

输出

1

生成的序列为 4,2,4,5,34,2,4,5,3。

样例 #2

输入

2 100 10

输出

2309

生成的序列为 78,3178,31。

样例 #3

输入

3 100 10

输出

89

生成的序列为 78,31,478,31,4。

样例 #4

输入

50 50000000 97

输出

50823796

数据范围

  • 对于 10%10\% 的数据,n,m≤100n,m\le100;
  • 对于 30%30\% 的数据,n≤100,m≤104n\le100,m\le10^4;
  • 对于 60%60\% 的数据,2≤m≤1072\le m\le10^7;
  • 对于 80%80\% 的数据,2≤m≤5×1072\le m\le5\times10^7;
  • 对于 100%100\% 的数据,50≤n≤10750\le n\le10^7,2≤m≤1082\le m\le10^8;
  • 0≤seed≤232−10\le seed\le2^{32}-1。