传染病（快速幂)

题目背景

新型病毒正在肆虐洛谷。

题目描述

91-DIVOC 正在广泛传播，珂学家 RyanLi 想要探究 91-DIVOC 的传染系数。

第一天有 a 个人被 91-DIVOC 感染，从第二天起，每个感染者都会向 q 个没有感染的人传播 91-DIVOC，使他们变为感染者。

举个例子，如果第一天有 3 人被感染，每个感染者每天向 2 个人传播病毒，那么第二天会有 3×2 个人被感染。第三天会有 3×2×2 个人被感染 ⋯ 以此类推。

定义传染系数为每天被感染 91-DIVOC 的人数的乘积，RyanLi 需要你求出 k 天内的传染系数。由于这个数很大，你只需要输出它对 722733748 取模的结果。

输入格式

输入一行三个整数k,a,q。

输出格式

输出一行一个整数，表示答案。

输入输出样例

输入

3 3 2

输出

216

分析可知：

每天感染人数：

• 第 1 天：a

• 第 2 天：a × q

• 第 3 天：a × q × q

• 第 4 天：a × q × q × q

• ……

• 第 k 天：a × q^(k-1)

传染系数 = 把这 k 天的人数全部乘起来

① 一共有多少个 a？

一共 k 天 →a 乘了 k 次

→ a × a × a × … × a =a^k

② 一共有多少个 q？

q 的指数是：0 + 1 + 2 + 3 + … + (k-1)

这是等差数列求和：

和 = k×(k-1) / 2

→ q 的总次数就是这个和

→q^( k×(k-1)/2 )

快速幂的理解

假如求2^5

正常计算思维：2x2x2x2x2

快速幂： 2^1 ​ 2^2 ​ 2^4 ​ 2^8

为什么快速幂是这样的？（自我思考，解释可能有误）

那么我们就可以深度思考一下二进制转化为十进制其中的奥妙

任意十进制都可以转化为二进制，并且二进制的进位速度非常快，这里所说的进位就是相当于十进制相加时候的满10进1

2^0--->2^1 进位1 2^1--->2^2 进位2 2^2--->2^3 进位4 ..... ..... 2^(n-1)--->2^n 进位2^(n-1)

所以根据这个特点我们就可以得出快速幂把暴力(O(n))求幂压缩到(O(logn))，专门解决超大指数求模问题，普通小指数两种方法差别不大(快速幂）

这里还有个知识点：我在学习汇编语言的时候，老师说过计算机编程时加法优于乘法（说法粗劣），详细原因如下：

底层开发 / 性能极致优化（手写汇编、内核、嵌入式、算法高频运算）这时候加法（+ 移位）优于原生乘法

执行效率：CPU 乘法指令时钟周期更长、延迟高，高频循环里差距会被放大；把x*n转成移位 + 加法是行业标准优化手法。

代码实现

import java.util.*; public class Test1{ static long mod = 722733748L; //计算a^b%mod static long MOD(long a, long b, long mod){ long res = 1; //存储乘法的结果 a %= mod; while(b>0){ if((b & 1) == 1)res = res*a%mod; //这里利用的是二进制,如果 b 是奇数，就把当前的 a 乘到结果里 a = a*a%mod; // a 变成自己的平方 b >>= 1; //相当于b/2,>> 是二进制右移，计算机算得更快 //b >>=1 等价整数除法b = b/2，位运算本身指令周期略短，是编译器友好写法 } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); long k = sc.nextLong(); long a = sc.nextLong(); long q = sc.nextLong(); //先计算a^k long r = MOD(a, k, mod); //计算指数0+1+2+...+k-1 long s = k*(k-1)/2; //计算q^s long t = MOD(q,s,mod); //最终答案 long result = r*t%mod; System.out.println(result); sc.close(); } }