HDU5667Sequence矩阵快速幂+费马小定理

f[1] &＃61; 1

f[2] &＃61; a ^ b

其实不是很好的去想到取log的 

两边同时取log

然后 F[2] &＃61; b  F[1] &＃61; 0

则 f[n] &＃61; a^(F[n]) % p  

费马小定理 &＃xff1a; 

① 判断素数&＃xff0c;对于大素数的判定&＃xff0c;Miller-Rabin 素数判定
②求解逆元 &＃xff0c;设a模p的逆元为x&＃xff0c;则a*x≡1(mod p) ,(a,p)&＃61;1;由费马小定理可以知道x&＃61;a^(p-2)
③对于计算ab(modp)ab(modp) 可简化
            对于素数p&＃xff0c;任取跟他互素的数a&＃xff0c;有a^(p-1)(mod p)&＃61;1
            所以任取b&＃xff0c;有a^b%p&＃61;a^(b%(p-1))(%p)从而简化运算。

本文来自 杨美人 的博客 &＃xff0c;全文地址请点击&＃xff1a;https://blog.csdn.net/qq_40679299/article/details/80596406?utm_source&＃61;copy

然后 f[n] &＃61; a^(F[n] mod (p - 1) ) mod p

代码&＃xff1a;

//
// HDU5667 - Sequence.cpp
// 数论
//
// Created by Terry on 2018/9/29.
// Copyright © 2018年 Terry. All rights reserved.
//#include
typedef long long LL;
long long read(){long long x &＃61; 0, f &＃61; 1;char ch&＃61;getchar();while(ch <&＃39;0&＃39; || ch > &＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;) f &＃61; -1; ch &＃61; getchar();}while(ch >&＃61; &＃39;0&＃39; && ch <&＃61; &＃39;9&＃39;){x &＃61; x * 10 &＃43; ch - &＃39;0&＃39;; ch &＃61; getchar();}return x * f;
}
const int maxn &＃61; 3;
LL mod;
struct Matrix{long long int m[maxn][maxn];
}unit;
Matrix operator * (Matrix a, Matrix b){Matrix ret;LL x;int n &＃61; 3;for(int i &＃61; 0; i }
void init_unit(){// 单位矩阵for(int i &＃61; 0; i }
Matrix pow_mat(Matrix a, LL n){Matrix ans &＃61; unit;while (n) {if(n & 1){ans &＃61; ans * a;}a &＃61; a * a;n >>&＃61; 1;}return ans;
}
LL multi(LL a, LL b, LL Mod){// a * b % ModLL ret &＃61; 0;while(b > 0){if(b & 1){ret &＃61; (ret &＃43; a) % Mod;}b >>&＃61; 1;a &＃61; (a <<1) % Mod;}return ret;
}LL quick_mod(LL a, LL b, LL Mod){LL ans &＃61; 1;while(b){if(b & 1){ans &＃61; multi(ans, a, Mod);b--;}b /&＃61; 2;a &＃61; multi(a, a, Mod);}return ans;
}
int main(){init_unit();LL T &＃61; read();while (T--) {LL n &＃61; read();LL a &＃61; read();LL b &＃61; read();LL c &＃61; read();mod &＃61; read();if(n &＃61;&＃61; 1){printf("1\n");}else if(n &＃61;&＃61; 2){printf("%lld\n", quick_mod(a, b, mod));}else{if(a % mod &＃61;&＃61; 0){printf("0\n");continue;}Matrix ans, A;A.m[0][0] &＃61; c; A.m[0][1] &＃61; 1; A.m[0][2] &＃61; 0;A.m[1][0] &＃61; 1; A.m[1][1] &＃61; 0; A.m[1][2] &＃61; 0;A.m[2][0] &＃61; 1; A.m[2][1] &＃61; 0; A.m[2][2] &＃61; 1;ans.m[0][0] &＃61; b; ans.m[0][1] &＃61; 0; ans.m[0][2] &＃61; b;mod--; // 费马小定理A &＃61; pow_mat(A, n - 2);ans &＃61; ans * A;mod&＃43;&＃43;;printf("%lld\n", quick_mod(a, ans.m[0][0]%(mod - 1), mod));}}return 0;
}