文章目录
- 快速幂
- 矩阵快速幂
- 慢速乘
- 例题
- HDU-2817
- HDU-3117
- XUJC-1395
int fastpow(int a, int n) {
int res = 1;
while (n) {
if (n & 1) //末位为1
res = (res * a) % mod;
a = (a * a) % mod;
n >>= 1; //n右移一位
}
return res;
}矩阵快速幂
struct matrix {
int a[maxn][maxn]; //矩阵a
matrix() { //构造时初始化
memset(a, 0, sizeof(a));
}
};
matrix multi(matrix x, matrix y) { //矩阵乘法
matrix res;
for (int i = 0; i < maxn; i )
for (int j = 0; j < maxn; j )
for (int k = 0; k < maxn; k )
res.a[i][j] = (res.a[i][j] x.a[i][k] * y.a[k][j]) % mod;
return res;
}
matrix fastm(matrix a, int n) { //矩阵快速幂
matrix res;
for (int i = 0; i < maxn; i )
res.a[i][i] = 1; //初始化为单位矩阵
while (n) {
if (n & 1)res = multi(res, a);
a = multi(a, a);
n >>= 1;
}
return res;
}慢速乘
慢速乘，顾名思义，之所以慢是因为把乘法拆成了若干次加法运算，但是我们可以在每次加法时对中间结果进行取模，所以可以防止大数相乘溢出，其原理同快速幂，不再赘述。
代码语言：javascript复制ll mul(ll a, ll b) {
ll res = 0;
while (b) {
if (b & 1)
res = (res a) % mod;
a <<= 1;
a %= mod;
b >>= 1;
}
return res;
}例题
HDU-2817
HDU-2817 A sequence of numbers
Problem Description Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help. Input The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence. You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing. Output Output one line for each test case, that is, the K-th number module (%) 200907. Sample Input 2 1 2 3 5 1 2 4 5 Sample Output 5 16
分析： 给出序列前3项，要求输出第n项，判断一下等差还是等比，等比的话套快速幂。
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
typedef long long ll;
#define mod 200907
ll fastpow(ll a, ll n) {
ll res = 1;
while (n) {
if (n & 1)
res = (res * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return res;
}
int main() {
ll n, a, b, c, k;
cin >> n;
while (n--) {
cin >> a >> b >> c >> k;
if (c - b == b - a)
cout << ((k - 3) * (b - a) c) % mod << "n";
else
cout << (fastpow(c / b, k - 1) * a) % mod << "n";
}
return 0;
}HDU-3117
HDU-3117 Fibonacci Numbers
Problem Description The Fibonacci sequence is the sequence of numbers such that every element is equal to the sum of the two previous elements, except for the first two elements f0 and f1 which are respectively zero and one. What is the numerical value of the nth Fibonacci number? Input For each test case, a line will contain an integer i between 0 and 108 inclusively, for which you must compute the ith Fibonacci number fi. Fibonacci numbers get large pretty quickly, so whenever the answer has more than 8 digits, output only the first and last 4 digits of the answer, separating the two parts with an ellipsis (“…”). There is no special way to denote the end of the of the input, simply stop when the standard input terminates (after the EOF). Sample Input 0 1 2 3 4 5 35 36 37 38 39 40 64 65 Sample Output 0 1 1 2 3 5 9227465 14930352 24157817 39088169 63245986 1023…4155 1061…7723 1716…7565
#include<bits/stdc .h> using namespace std; #define mod 10000 //取后四位 const int maxn = 2; //2阶矩阵 int f[40], n; struct matrix { int a[maxn][maxn]; matrix() { memset(a, 0, sizeof(a)); } }; matrix multi(matrix x, matrix y) { matrix res; for (int i = 0; i < maxn; i ) for (int j = 0; j < maxn; j ) for (int k = 0; k < maxn; k ) res.a[i][j] = (res.a[i][j] x.a[i][k] * y.a[k][j]) % mod; return res; } matrix fastm(matrix a, int n) { matrix res; for (int i = 0; i < maxn; i ) res.a[i][i] = 1; while (n) { if (n & 1)res = multi(res, a); a = multi(a, a); n >>= 1; } return res; } void init() { f[0] = 0; f[1] = 1; for (int i = 2; i < 40; i ) f[i] = f[i - 1] f[i - 2]; } int main() { init(); while (~scanf("%d",&n)) { if (n < 40) { printf("%dn", f[n]); continue; } double pre = log10(1.0 / sqrt(5.0)) (double)n * log10((1.0 sqrt(5.0)) / 2.0); pre = pre - (int)pre; printf("%d", (int)(1000.0 * pow(10.0, pre))); printf("..."); matrix last; last.a[0][0] = last.a[0][1] = last.a[1][0] = 1; last = fastm(last, n); printf("%0.4dn", last.a[0][1]);//注意巨坑：前导0 } return 0; }
XUJC-1395
XUJC-1395数列乘积
样例输入 2 3 100 2 5 7 3 10 2 5 7 样例输出 70 0 HINT 2 × 5 × 7 = 70
分析： 首先用字符串数组读入数，然后取模，使其范围缩小至1e18，然后套用慢速乘即可，
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 100005;
int t, n;
ll mod, ans, y;
char x[maxn];
ll getmod(char* x) {
int lx = strlen(x);
ll yu = 0;
for (int i = 0; i < lx; i ) {
yu = (yu * 10) x[i] - '0';
if (yu >= mod)yu %= mod;
}
return yu;
}
ll mul(ll a, ll b) {
ll res = 0;
while (b) {
if (b & 1)
res = (res a) % mod;
a <<= 1;
a %= mod;
b >>= 1;
}
return res;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%lld", &n, &mod);
scanf("%s", x);
ans = getmod(x);
bool tag = false;
for (int i = 1; i < n; i ) {
scanf("%s", x);
if (tag)continue;
y = getmod(x);
ans = mul(ans, y);
if (ans == 0)tag = true;
}
printf("%lldn", ans);
}
return 0;
}原创不易，请勿转载（
本不富裕的访问量雪上加霜） 博主首页：https://blog.csdn.net/qq_45034708 如果文章对你有帮助，记得一键三连❤
