薛XX后代的IQ CSU1597【循环节】或【快速幂】

现在给定X和Y，还有药的属性A、B和P，现在他想知道他的N代子孙的IQ（儿子是第一代，孙子是第二代）。

Input
第一行包含一个整数T（T<=100），表示数据组数 每组数据只有一行，包含六个整数X,Y,A,B,P,N（1 ≤ X, Y ≤ 300,1 ≤ A, B ≤ 30, 1≤ P ≤ 300 , 1 ≤ N < 1000000000），含义如题目所述
Output
针对每组数据，输出第N代子孙的智商。

Sample Input

Sample Output

【思路】
本题有两种解法：

1. 循环节
   由题显然可以看出，P在1-300之间，则结果一定会在1-90000之间出现循环节，注意是连续的两组数据要同时和之前出现的一组数据相同，才被确认为出现了循环节。另外，循环节不一定是从0,1开始，可能呈6字形，也即从数据的中间开始出现循环，八戒影院这种情况一定要考虑。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = 90009;

int ans[maxn+2];

int vis[303][303];

int main()

{

    int t;

    scanf("%d", &t);

    int x, y, a, b, p, n;

    while(t--){

        memset(vis, -1, sizeof(vis));

        scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &p, &n);

        ans[0] = y;

        ans[1] = (a * x + b * y) % p;

        vis[ans[0]][ans[1]] = 0;

        int start;

        int circle;

        for(int i = 2; i < maxn; i++){

            ans[i] = (a * ans[i-2] + b * ans[i-1]) % p;

            if(vis[ans[i-1]][ans[i]] != -1){

                start = vis[ans[i-1]][ans[i]];

                circle = i - 1 - start;

                break;

            }

            else

                vis[ans[i-1]][ans[i]] = i-1;

        }

        cout << ans[start + (n - start) % circle] << endl;

    }

    return 0;

}

1. 快速幂
   这种类似斐波那契的数据类型，可以用快速幂来解决。要注意的是初始矩阵的初始化不能出错。然后再写一个矩乘函数就行了。

代码如下：

 

#include<cstdio>

#include<iostream>

#include<string>

#include<set>

using namespace std;

typedef long long LL;

int mod;

int x, y, p, q;

struct Node{LL m[3][3];};

void Init(Node &t, Node &a){

    t.m[1][1] = y;

    t.m[2][2] = 0;

    t.m[1][2] = x;

    t.m[2][1] = 0;

    a.m[1][1] = q;

    a.m[1][2] = 1;

    a.m[2][1] = p;

    a.m[2][2] = 0;

}

Node mul(Node a, Node b){

    Node tem;

    tem.m[1][1] = (a.m[1][1] * b.m[1][1] + a.m[1][2] * b.m[2][1]) % mod;

    tem.m[1][2] = (a.m[1][1] * b.m[1][2] + a.m[1][2] * b.m[2][2]) % mod;

    tem.m[2][1] = (a.m[2][1] * b.m[1][1] + a.m[2][2] * b.m[2][1]) % mod;

    tem.m[2][2] = (a.m[2][1] * b.m[1][2] + a.m[2][2] * b.m[2][2]) % mod;

    return tem;

}

int main (){

    int n;

    int tim;

    scanf("%d", &tim);

    Node t, a;

    while(tim--){

        scanf("%d%d%d%d%d%d",www.rcsx.org &x, &y, &p, &q, &mod, &n);

        Init(t, a);

        while(n){

            if(n&1) t = mul(t,a);

            a = mul(a, a);

            n >>= 1;

        }

        cout << t.m[1][1] % mod << endl;

    }

    return 0;

}