[matrix multiplication] [noi 2012] [cogs963] random number generator

Hello everyone , I meet you again , I'm the king of the whole stack .

963. [NOI2012] Random number generator

**    Input file ：randoma.in    The output file ：randoma.out    Simple comparison 
 The time limit ：1 s    Memory limit ：128 MB

Copy

**【 Problem description and narration 】

Dong Dong has been fascinated by random algorithms recently , And random number is the basis of generating random algorithm . Dong Dong is going to use the linear congruence method （Linear Congruential Method） To generate a random sequence of numbers . Such a method requires setting four non negative integer parameters m,a,c,X[0], A series of random numbers are generated according to the following formula {Xn}：

X[n+1]=(aX[n]+c) mod m

Copy

among mod m Represents the previous number divided by m The remainder of . From this formula, we can see , The next number in this sequence is always generated by the previous number .

The sequence generated by this method has the property of random sequence . So this method is widely used , Including frequently used C++ and Pascal The library function that generates random numbers uses the same method .

Dong Dong knows that the sequence generated in this way has good randomness , Just anxious, he still wants to know as soon as possible X[n] How much is the .

Because the random number needed by every building is 0,1,…,g-1 Between , He needs to X[n] Divide g Take the remainder and get the number he wants , namely X[n] mod g, You just have to tell Dong Dong the number he wants X[n] mod g How much is enough .

【 Input format 】

Input file randoma.in It includes 6 An integer with spaces m,a,c,X[0],n and g, among a,c,X[0] Is a nonnegative integer .m,n,g It's a positive integer. .

【 Output format 】

output to a file randoma.out in , Output a number , namely X[n] mod g

【 Example input 】

11 8 7 1 5 3

Copy

【 Example output 】

2

Copy

【 Example illustrate 】

 Calculated X[n]=X[5]=8, so (X[n] mod g) = (8 mod 3) = 2

Copy

【 Data scale 】

40% Data in m Prime number 
30% Data in m And a-1 Coprime 

50% Data in n<=10^6
100% Data in n<=10^18

40% The data of m,a,c,X[0]<=10^4
85% The data of m,a,c,X[0]<=10^9
100% Data in m,a,c,X[0]<=10^18

100% Data in g<=10^8

 For all data ,n>=1,m>=1,a>=0,c>=0,X[0]>=0,g>=1.

Copy

Answer key ：

Simpler matrix multiplication , For two matrices ：

A[a,c0,1]

B[X[n−1]1]

obviously ,X[n] It can be obtained by multiplying these two matrices ： A∗B=C[X[n]1]

So for X[n], We can ask ： An∗[X[0]1]

It is necessary to write about high-speed travel , Because ordinary passengers will explode ... （PS: High speed multiplication is almost the same as high speed exponentiation , Just put * Change to +）

Code：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long A[2][2]={{0,0},{0,1}},B[2][2]={{0,0},{1,0}},C[2][2]={0};
long long n,g,m,nn;
long long kc(long long x,long long y){
    long long z=0;
    x%=m; y%=m;
    if (x<y) swap(x,y);
    while (y){
        if (y&1) z=(z+x)%m;
        x=(2*x)%m;
        y>>=1;
    }
    return z;
}
int main(){
    scanf("%lld%lld%lld%lld%lld%lld",&m,&A[0][0],&A[0][1],&B[0][0],&n,&g);
    nn=n;
    while (nn){
        if (nn&1){
            memset(C,0,sizeof(C));
            for (int i=0; i<2; i++)
                for (int j=0; j<2; j++)
                    for (int k=0; k<2; k++)
                        C[i][j]=(C[i][j]+kc(A[i][k],B[k][j]))%m;
            for (int i=0; i<2; i++)
                for (int j=0; j<2; j++)
                    B[i][j]=C[i][j];
        }
        nn>>=1;
        memset(C,0,sizeof(C));
        for (int i=0; i<2; i++)
            for (int j=0; j<2; j++)
                for (int k=0; k<2; k++)
                    C[i][j]=(C[i][j]+kc(A[i][k],A[k][j]))%m;
        for (int i=0; i<2; i++)
            for (int j=0; j<2; j++)
                A[i][j]=C[i][j];
    }
    printf("%lld\n",B[0][0]%g);
    return 0;
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/116386.html Link to the original text ：https://javaforall.cn