)
题目背景
新型病毒正在肆虐洛谷。
题目描述
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(); } }
