题目链接:题目链接
题面:
小王一直都想在太空遨游,但是现在的他并没有这个超能力,所以他买了个 “自由弹簧” 打算过过瘾。
这个 ”自由弹簧“ 在初次使用时,会将小王弹射到 N
( 2 <= N <= 200000) 米的高度,当弹簧落地时,会触发 ”自由弹簧“ 的超能力,会自动将小王弹射到 N * N
米的高度!
”自由弹簧“ 的生产者设置了一道保护机制,当弹射高度 N
超过 100000007 米时,会自动将高度降低 N % 100000007
米的位置,以此保证小王的安全。
但 ”自由弹簧“ 也有使用寿命,当落地 M
( 2 <= M <= 200000)次(不含初次使用时的落地情况)之后,将不会再进行弹射,最终会将小王安全送回地面,并且自动消失。
小王想知道,当 ”自由弹簧“ 最后一次弹射时,会弹射到多高的高度 X
?(米,如 X 超过100000007 ,则求自动降低后的高度)
本次挑战需要你至少了解一些 Java 中整数的基本运算和幂运算,了解快速幂的计算流程。
知识点
- 整数的基本运算
- 整数幂运算
- 快速幂取模
初始代码
public class AMain { private static final long MOD = 100000007; // 请勿修改 doWork() 的方法名和参数类型 public static long doWork(long n,long m) { long ans = 1; //代码编辑区 开始 //代码编辑区 结束 return ans; } public static void main(String[] args) { //测试用例 System.out.printf((Objects.equals(2048L,doWork(2, 10)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",2,10,doWork(2, 10)); System.out.printf((Objects.equals(729L,doWork(3, 5)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",3,5,doWork(3, 5)); System.out.printf((Objects.equals(29516713L,doWork(9, 11)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",3,5,doWork(9, 11)); System.out.printf((Objects.equals(99898098L,doWork(99999, 88888)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",99999,88888,doWork(99999, 88888)); } }
样例说明
输入首次弹射高度 N 和弹射次数 M,输出最后一次弹射的高度。
如首次弹射高度 N = 2,弹射次数为 10,最后一次弹射的高度为 2048 米,则输出 2048。
如首次弹射高度 N = 3,弹射次数为 5,最后一次弹射的高度为 729 米,则输出 729。
如首次弹射高度 N = 9,弹射次数为 11,最后一次弹射的高度为 29516713 米,则输出 29516713 。
题解
签到题,考察快速幂取模,对于初次使用高度 N
和使用寿命次数 M
,最后一次弹射高度等于 N 的 (M + 1) 次幂对 100000007 取模
。
参考代码如下:
import java.util.Objects; public class AAns { private static final long MOD = 100000007; public static long doWork(long n,long m) { long ans = 1; //代码编辑区 开始 m ++; long number = n % MOD; while(m > 0) { if((m & 1) > 0) { ans = (ans * number) % MOD; } number = (number * number) % MOD; m /= 2; } //代码编辑区 结束 return ans; } public static void main(String[] args) { //测试用例 System.out.printf((Objects.equals(2048L,doWork(2, 10)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",2,10,doWork(2, 10)); System.out.printf((Objects.equals(729L,doWork(3, 5)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",3,5,doWork(3, 5)); System.out.printf((Objects.equals(29516713L,doWork(9, 11)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",3,5,doWork(9, 11)); System.out.printf((Objects.equals(99898098L,doWork(99999, 88888)) ? "【√正确】" : "【X错误】") + "初始速度%d,寿命%d次,最后弹射高度%d\n",99999,88888,doWork(99999, 88888)); } }
总结
要 AC 本题,必须学会快速幂取模的算法。
使用快速幂取模可以将原有的 O(N)的时间复杂度降为 O(log (2,N)),从而通过本题。