华硕编程竞赛11月JAVA专场 A题自由弹簧题解

妖狐艹你老母 2023-09-24 15:19 90阅读 0赞

> **作者主页**：[Designer 小郑][Designer]  
> **作者简介**：软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者，在校期间参加PAT乙级考试获得满分，三年ACM竞赛经验，斩获国奖两项，省奖五项。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！  
> **主打方向**：Vue、SpringBoot、微信小程序

题目链接：[题目链接][Link 1]

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题面： ###

小王一直都想在太空遨游，但是现在的他并没有这个超能力，所以他买了个 “自由弹簧” 打算过过瘾。

这个 ”自由弹簧“ 在初次使用时，会将小王弹射到 `N`（ 2 <= N <= 200000） 米的高度，当弹簧落地时，会触发 ”自由弹簧“ 的超能力，会自动将小王弹射到 `N * N` 米的高度！

”自由弹簧“ 的生产者设置了一道保护机制，当弹射高度 `N` 超过 100000007 米时，会自动将高度降低 `N % 100000007` 米的位置，以此保证小王的安全。

但 ”自由弹簧“ 也有使用寿命，当落地 `M` （ 2 <= M <= 200000）次（不含初次使用时的落地情况）之后，将不会再进行弹射，最终会将小王安全送回地面，并且自动消失。

小王想知道，当 ”自由弹簧“ 最后一次弹射时，会弹射到多高的高度 `X` ？（米，如 X 超过100000007 ，则求自动降低后的高度）

本次挑战需要你至少了解一些 Java 中整数的基本运算和幂运算，了解快速幂的计算流程。

### 知识点 ###

*  整数的基本运算
 *  整数幂运算
 *  快速幂取模

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 初始代码 ###

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));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 样例说明 ###

输入首次弹射高度 N 和弹射次数 M，输出最后一次弹射的高度。

如首次弹射高度 N = 2，弹射次数为 10，最后一次弹射的高度为 2048 米，则输出 2048。

如首次弹射高度 N = 3，弹射次数为 5，最后一次弹射的高度为 729 米，则输出 729。

如首次弹射高度 N = 9，弹射次数为 11，最后一次弹射的高度为 29516713 米，则输出 29516713 。

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 题解 ###

签到题，考察快速幂取模，对于初次使用高度 `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));
        }
    }

![在这里插入图片描述][d20811fc24154b148e6372d8bd803dab.png_pic_center]

### 总结 ###

要 AC 本题，必须学会快速幂取模的算法。

使用快速幂取模可以将原有的 O（N）的时间复杂度降为 O（log (2，N)），从而通过本题。

![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[Link 1]: https://www.lanqiao.cn/contests/lqENT05/challenges/
[d20811fc24154b148e6372d8bd803dab.png_pic_center]: https://img-blog.csdnimg.cn/d20811fc24154b148e6372d8bd803dab.png#pic_center
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center