Description

栋栋最近迷上了随机算法, 而随机数生成是随机算法的基础. 栋栋准备使用线性同余法来 生成一个随机数列, 这种方法需要设置四个非负参数 \(m, a, c, X_0\), 按照下面的公式来 生成出一系列随机数 \(\{X_n\}\):

\[X_{n+1} = (a \cdot X_n + c) \bmod m\]

其中 \(\bmod m\) 表示前面的数除以 \(m\) 的余数. 从这个式子可以看出, 这个序列的下一个 数总是由上一个数生成的.

用这种方法生成的序列具有随机序列的性质, 因此这种方法被广泛地使用, 包括常用的 C++和 Pascal 的产生随机数的库函数使用的也是这种方法.

栋栋知道这样产生的序列具有良好的随机性, 不过心急的他仍然想尽快知道 \(X_n\) 是多少. 由于栋栋需要的随机数是 \(0, 1, \ldots, g-1\) 之间的, 他需要将 \(X_n\) 除以 \(g\) 取余 得到他想要的数, 即 \(X_n \bmod g\), 你只需要告诉栋栋他想要的数 \(X_n \bmod g\) 是多少就可以了.

Input

包含 \(6\) 个用空格分割的整数 \(m, a, c, X_0, n, g\), 其中 \(a, c, X_0\) 是非负整数,\(m, n, g\) 是正整数.

Output

输出一个数, 即 \(X_n \bmod g\)

Sample Input

11 8 7 1 5 3

Sample Output

2

Explanation

首先 BZOJ 不给题目描述我也是醉了......

然后到 Vijos 上找了一发终于找到了, 题号 Vijos P1725.

看一眼就是矩阵乘法对不对......

然后题解我就不写了, 矩阵构造如下:

\[\begin{bmatrix} a&c\\ 0&1 \end{bmatrix}\]

但是这道题的乘法巨坑, 如果不开高精度就过不去, 因为中间乘法就是 int64_t 都会溢出~ 所以随便写了个二分乘法 (快速乘, 雾) 水过了.

然后想了想, 能不能用 __int128 大法好呢...... 就在本机上瞎搞了一发, 注意 scanf(...) 和 istream& 等操作是原生不资磁 __int128 的, 所以还需要先用 int64_t 读入最后 强制类型转换. 本机上这段代码是测过的:

llf l_modr, l_a, l_c, l_x0, l_n, l_g;
scanf("%lld%lld%lld%lld%lld%lld", &l_modr, &l_a, &l_c, &l_x0, &l_n, &l_g);
modr = l_modr, a = l_a, c = l_c, x0 = l_x0, n = l_n, g = l_g;

用的是 PyJudge 手动 AC, 然而交到耒阳上得到 CE, 那就没什么我的事了, 还是乖乖手写 高精度吧==|||

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

lli modr, a, c, x0, n, g;

// Ensure precision without the need of a BigInteger library.
lli mult_hp(lli a, lli b)
{
    lli res = 0;
    for (; b; b >>= 1, a = (a + a) % modr)
        if (b & 1)
            res = (res + a) % modr;
    return res;
}

struct matrix {
    lli arr[3][3];
    matrix& operator *= (const matrix& b)
    {
        static lli c[3][3];
        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++) {
                c[i][j] = 0;
                for (int k = 1; k <= 2; k++)
                    c[i][j] += mult_hp(arr[i][k], b.arr[k][j]);
            }
        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
                arr[i][j] = c[i][j] % modr;
        return *this;
    }
    matrix(lli _1, lli _2, lli _3, lli _4)
    {
        arr[1][1] = _1, arr[1][2] = _2;
        arr[2][1] = _3, arr[2][2] = _4;
        return ;
    }
    matrix(lli _1)
    {
        arr[1][1] = _1; arr[1][2] = 0;
        arr[2][1] = 0; arr[2][2] = _1;
        return ;
    }
};

matrix operator ^ (matrix a, lli powr)
{
    matrix c( 1 );
    for (; powr > 0; powr >>= 1, a *= a)
        if (powr & 1)
            c *= a;
    return c;
}

int main(int argc, char** argv)
{
    scanf("%lld%lld%lld%lld%lld%lld", &modr, &a, &c, &x0, &n, &g);
    matrix make (
        a, c,
        0, 1 );
    make = make ^ n;
    lli res = mult_hp(make.arr[1][1], x0) + make.arr[1][2];
    res %= modr;
    res %= g;
    printf("%lld\n", res);
    return 0;
}