E – 随机数生成器

LibreOJ - 2670

直接模拟矩阵乘法即可

但是，注意数据范围，我们long long乘法会炸精度，因此采用快速乘。

快速乘，类似快速幂的思想，大概就是把乘号改加号

int mul(int x,int y){
    int z = 0;
    while(y){
        if(y & 1) z = z + x;
        y >>= 1;
        x = x + x;
    }
    return z;
}

#include<bits/stdc++.h>
using namespace std;

long long mod,A,C,x0,xn,n,G;

struct jz{
    long long g[4][4];
    void init(){
        memset(g,0,sizeof(g));
    }
    void one(){
        memset(g,0,sizeof(g));
        for(int i = 1; i <= 2; ++ i) g[i][i] = 1;
    }
};
long long mul(long long x,long long y){
    long long z = 0;
    while(y){
        if(y & 1) z = (z + x) % mod;
        y >>= 1;
        x = (x + x) % mod;
    } 
    return z;
}
jz operator * (jz a, jz b){
    jz c; c.init();
    for(int i = 1; i <= 2; ++ i)
    for(int j = 1; j <= 2; ++ j)
    for(int k = 1; k <= 2; ++ k)
    c.g[i][j] = ( c.g[i][j] + mul(a.g[i][k], b.g[k][j])) % mod;
    return c;
}
jz ksm(jz x,long long y){
    jz z; z.one();
    while(y){
        if(y & 1) z = z * x;
        y >>= 1;
        x = x * x;
    }
    return z;
}

jz a;

int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&mod,&A,&C,&x0,&n,&G);

    a.g[1][1] = A; a.g[1][2] = 1;
    a.g[2][1] = 0; a.g[2][2] = 1;

    a = ksm(a, n);

    long long xn = (mul(a.g[1][1],x0) + mul(a.g[1][2],C))% mod;

    printf("%lld\n",(xn % G + G) % G);

    return 0;
}