/* * [题意] * 略 * [解题方法] * 设g为所求。 * 观察可知:g(1) = a; g(2) = b; g(3) = a*b; g(4) = a*(b^2); g(5) = (a^2)*(b^3)... * 易得:g(n) = g(n-1)*g(n-2) * 所以对于a的幂或b的幂有:f(n) = f(n-1)+f(n-2) * 设矩阵A = |1 1| * |1 0| * 令B = A^(n-2),得: * g(n)中b的幂 = B[0][0]; * g(n)中a的幂 = B[0][1]; * {上述为斐波那契矩阵的性质} * 由于是幂,所以矩阵乘法时需要用到降幂公式进行取余 * 详情请参考:http://972169909-qq-com.iteye.com/blog/1278667 */ #include <iostream> #include <stdio.h> #include <string.h> using namespace std; #define LL long long #define FF(i, n) for(int i = 0; i < n; i++) #define M 2 int ret[M][M], mod, phi; int init[M][M]; int ss[M][M] = {1, 1, 1, 0}; void ini(int n) { FF(i, n) FF(j, n) init[i][j] = ss[i][j]; } void matmul(int a[][M], int b[][M], int n) { LL tp[M][M] = {0}; FF(i, n) FF(k, n) if(a[i][k]) FF(j, n) if(b[k][j]) { tp[i][j] = tp[i][j] + (LL)a[i][k]*b[k][j]; //降幂公式的条件 if (tp[i][j] >= phi) tp[i][j] = tp[i][j] % phi + phi; } FF(i, n) FF(j, n) a[i][j] = tp[i][j]; } void qmod(int n, int b) { FF(i, n) FF(j, n) ret[i][j] = (i==j); for ( ; b; b >>= 1) { if (b & 1) matmul(ret, init, M); matmul(init, init, M); } } LL cal(LL a, LL b) { LL res = 1; for ( ; b; b >>= 1) { if (b & 1) res = res * a % mod; a = a * a % mod; } return res; } int Euler(int n) //欧拉函数 { int i, res = n; for (i = 2; (LL)i * i <= n; i++) { if (n % i == 0) { do n /= i; while (n % i == 0); res = res - res/i; } } if (n > 1) res = res - res/n; return res; } int main() { int t, cc = 0, n, a, b; cin >> t; while (t--) { cin >> a >> b >> mod >> n; cout << "Case #" << (++cc) << ": "; if (n == 1) { cout << a%mod << endl; continue; } if (n == 2) { cout << b%mod << endl; continue; } phi = Euler(mod); ini(M); qmod(M, n-2); int ans = cal(a, ret[0][1])*cal(b, ret[0][0]) % mod; cout << ans << endl; } return 0; }
相关推荐
数据来源:中国电力统计NJ-2021版
数据来源:中国电力统计NJ-2021版
词根单词 2.2.4 修改版.apk
毕业论文-基于JSP的个人通讯录管理系统设计与实现.docx
数据来源:中国电力统计NJ-2021版
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
数据来源:中国电力统计NJ-2021版
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
数据来源:中国人口与就业统计NJ-2023版
图书借阅管理系统设计与实现及论大学生写作能力.docx
Smart继电器编程器操作手册
毕业设计论文-基于C的人事管理系统设计与实现.docx
数据来源:中国劳动统计NJ-2023版
OPCEV096IPHT手册
数据来源:中国电力统计NJ-2021版
数据来源:中国人口与就业统计NJ-2023版
数据来源:中国人口与就业统计NJ-2023版
基于matlab实现应用遗传算法针对物流配送车辆路径规划问题进行求解.rar
Node.js,简称Node,是一个开源且跨平台的JavaScript运行时环境,它允许在浏览器外运行JavaScript代码。Node.js于2009年由Ryan Dahl创立,旨在创建高性能的Web服务器和网络应用程序。它基于Google Chrome的V8 JavaScript引擎,可以在Windows、Linux、Unix、Mac OS X等操作系统上运行。 Node.js的特点之一是事件驱动和非阻塞I/O模型,这使得它非常适合处理大量并发连接,从而在构建实时应用程序如在线游戏、聊天应用以及实时通讯服务时表现卓越。此外,Node.js使用了模块化的架构,通过npm(Node package manager,Node包管理器),社区成员可以共享和复用代码,极大地促进了Node.js生态系统的发展和扩张。 Node.js不仅用于服务器端开发。随着技术的发展,它也被用于构建工具链、开发桌面应用程序、物联网设备等。Node.js能够处理文件系统、操作数据库、处理网络请求等,因此,开发者可以用JavaScript编写全栈应用程序,这一点大大提高了开发效率和便捷性。 在实践中,许多大型企业和组织已经采用Node.js作为其Web应用程序的开发平台,如Netflix、PayPal和Walmart等。它们利用Node.js提高了应用性能,简化了开发流程,并且能更快地响应市场需求。
数据来源:中国人口与就业统计NJ-2023版