传染病（快速幂)

题目背景新型病毒正在肆虐洛谷。题目描述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② 一共有多少个 qq 的指数是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进12^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(b0){ 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); //计算指数012...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(); } }