JohnArt

用户名：dotcpp0677024

访问量：2271

签　名：

等　　级
排　　名	20516
经　　验	692
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	杭州电子科技大学
专　　业

　　自我简介：

TA的其他文章

3168: 蓝桥杯2023年第十四届省赛真题-太阳(Java满分题解)
浏览：1058

3162: 蓝桥杯2023年第十四届省赛真题-互质数的个数
浏览：700

你可能喜欢

3162: 蓝桥杯2023年第十四届省赛真题-互质数的个数

　　作者: JohnArt　　　　发表时间：2023-11-07 23:02:00 浏览：700　|　评论：1　

原题链接：蓝桥杯2023年第十四届省赛真题-互质数的个数

这道题测试样例的答案好像出了点问题，所以为了在这里发题解真的费了一番功夫......大家做完之后可以去蓝桥的官网测试
![](/image_editor_upload/20231107/20231107104915_54765.jpg)
网址：https://www.lanqiao.cn/problems/?first_category_id=1&page=1&sort=students_count
题号是**3522**，或者直接搜这道题的名字**互质数的个数**就能找到了
#### 接下来是解题思路：
欧拉函数具体的原理就不讲了，有兴趣的可以去知乎看看。网址：https://zhuanlan.zhihu.com/p/151756874
这里我们只用用到一个公式就行
![](/image_editor_upload/20231107/20231107105107_71473.jpg)
可以发现，如果我们要计算小于a^b的与a^b互质的数数量，我们只用先算出小于a的与a互质数个数，然后乘a^(b - 1)即可，例如
![](/image_editor_upload/20231107/20231107105935_47203.jpg)
#### 代码实现：
```java
import java.util.Scanner;

public class Main {
    static final int MOD = 998244353;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int a1 = a;
        long b = sc.nextLong();
        long ans = 1;
        for (int i = 2; i <= a; i++) {
            int times = 0;
            while(a % i == 0){
                if(times == 0) {
                    ans = ans * (i - 1) % MOD;
                    a /= i;
                    times++;
                }
                else{
                    ans = ans * i % MOD;
                    a /= i;
                }
            }
        }
        ans = ans * qpow(a1 , b - 1) % MOD;
        System.out.println(ans);
    }

public static long qpow(long a, long b) {  // 求a的b次方
        long pow = 1;
        for (; b > 0; b >>= 1) {
            if ((b & 1) == 1) pow = pow * a % MOD;
            a = a * a % MOD;
        }
        return pow;
    }
}

```

0.0分

6 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

杨雨彤

你好，不明白为什么那样求a的互质数。能解释一下吗？谢谢

2024-01-22 15:20:23

JohnArt

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

1065

C二级辅导-等差数列（C++代码）

C二级辅导-进制转换（C语言代码）

【蟠桃记】（C语言代码）

3162: 蓝桥杯2023年第十四届省赛真题-互质数的个数

评论区

精彩推荐

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

JohnArt

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

1065

C二级辅导-等差数列 （C++代码）

C二级辅导-进制转换 （C语言代码）

【蟠桃记】 （C语言代码）

3162: 蓝桥杯2023年第十四届省赛真题-互质数的个数

评论区

精彩推荐

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题5.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C二级辅导-等差数列（C++代码）

C二级辅导-进制转换（C语言代码）

【蟠桃记】（C语言代码）

　　评论区

求圆的面积（C语言代码）

Tom数（C语言代码）