HDU 5667 构造矩阵快速幂
2024-09-23 17:29:16
HDU 5667 构造矩阵快速幂
题目描述
解析
我们根据递推公式
设
则可得到Q的指数关系式
求Q构造矩阵
同时有公式
其中φ为欧拉函数,且当p为质数时有
代码
#include <cstdio>
using namespace std;
long long pow_mod(long long a, long long p, long long mod) {
if (p == 0) return 1;
long long ans = pow_mod(a, p / 2, mod);
ans = (ans * ans) % mod;
if (p % 2) ans = (ans * a) % mod;
return ans;
}
long long get_p(long long c, long long n, long long mod) {
long long ans[3][3] = {{0, 0, 0}, {1, 0, 0}, {1, 0, 0}};
long long a[3][3] = {{0, 1, 0}, {1, c, 1}, {0, 0, 1}};
long long b[3][3];
while (n) {
if (n & 1) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
b[i][j] = 0;
for (int k = 0; k < 3; k++) {
b[i][j] += a[i][k] * ans[k][j];
b[i][j] %= mod;
}
}
}
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
ans[i][j] = b[i][j];
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
b[i][j] = 0;
for (int k = 0; k < 3; k++) {
b[i][j] += a[i][k] * a[k][j];
b[i][j] %= mod;
}
}
}
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
a[i][j] = b[i][j];
n >>= 1;
}
return ans[1][0];
}
int T;
long long n, a, b, c, p;
long long phi;
int main() {
scanf("%d", &T);
while (T--) {
scanf("%I64d %I64d %I64d %I64d %I64d", &n, &a, &b, &c, &p);
if (n <= 2) phi = n - 1;
else phi = get_p(c, n - 2, p - 1);
printf("%I64d\n", pow_mod(pow_mod(a, b, p), phi, p));
}
return 0;
}
最新文章
- Linux学习笔记（16）shell基础之Bash变量
- (转)Javascript匿名函数的写法、传参、递归
- 在Android中开源类库使用过程中兼容性等问题的讨论
- Python-str函数
- Simple Chroma Key 0.1.16 图片抠像(vs2003) 无任何插件
- easyfinding（codevs 3280）
- Scrum会议1(Beta版本)
- HTML——表格table标签，tr或者td
- HDU P4578 Transformation
- DevExpress XtraGrid RepositoryItemCheckEdit 复选框多选的解决方法
- SRM 405(1-250pt, 1-500pt)
- Guzzle php resetful webservice farmework
- jQuery学习-事件之绑定事件（二）
- Windows 8实例教程系列 - 开篇
- Django入门实践（一）
- Java日期工具类，Java时间工具类，Java时间格式化
- C#中float, double的精度问题
- 记录CentOS环境下将Solr部署到Tomcat
- echarts中地图提示"TypeError：i is undefined"
- 安装 xadmin 报错: Command "python setup.py egg_info" failed with error code 1 in C:\Users\Python\AppData\Local\Temp\pip-install-1k1byg0p\xadmin\