解释清晰，通俗易懂。一步一个脚印带着大家完成

1370 阅读 4 评论 0 点赞

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

[[#具体内容可以参考我的CSDN：](https://blog.csdn.net/weixin_43554580/article/details/130236509?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22130236509%22%2C%22source%22%3A%22weixin_43554580%22%7D "[#具体内容可以参考我的CSDN：")

https://blog.csdn.net/weixin_43554580/article/details/130236509?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22130236509%22%2C%22source%22%3A%22weixin_43554580%22%7D

# 如图所知，CSDN上有很全面的讲解，希望大家支持一下。
![](/image_editor_upload/20230419/20230419100435_42545.png)
# 原题链接
https://blog.csdn.net/weixin_43554580/article/details/130236509?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22130236509%22%2C%22source%22%3A%22weixin_43554580%22%7D

## 解析：
（1）首先大家要知道什么叫互质：
![在这里插入图片描述](https://img-blog.csdnimg.cn/1a60ea5134a8437e9915a1db87e92fd4.png)
以及它们的性质：
![在这里插入图片描述](https://img-blog.csdnimg.cn/425424c0f3b144daaae1539e56339083.png)
## 欧拉函数
在数论中，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。

> 例如φ(8) = 4，因为1,3,5,7均和8互质。
> 
> 也可以从简化剩余系的角度来解释，简化剩余系(reduced residue system)也称既约剩余系或缩系，是m的完全剩余系中与m互素的数构成的子集，如果模m的一个剩余类里所有数都与m互素，就把它叫做与模m互素的剩余类。在与模m互素的全体剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模m的一个简化剩余系。
> 
> （1，3，5，7）就构成了8的一个简化剩余系。

[参考链接：](https://zhuanlan.zhihu.com/p/151756874) https://zhuanlan.zhihu.com/p/151756874

```c
//package Dotcpp;

import java.io.*;
import java.util.Scanner;

public class Main {
	private static long mod = 998244353L;
	private static long a,b,res;

public static void main(String[] args) throws Exception {
		Scanner scanner = new Scanner(System.in);
		a = scanner.nextLong();
		b = scanner.nextLong();
		long n = Euler_pow(a,b);

res = n;
		for (int i = 2; i <= n / i; i++) {
			if (n % i == 0) {
				while (n % i == 0) {
					n /= i;
					n%=mod;
				}
				res = (res - res / i);
				res%=mod;
			}
		}
		if (n > 1) {
			res = (res - res / n);
			res%=mod;
		}
		scanner.close();
		System.out.println(res%=mod);
	}

private static long Euler(long n) {
		long res = n;
		for (long i = 2; i * i <= n; ++i) {
			if (n % i == 0) {
				res = res / i * (i - 1);
				while (n % i == 0) {
					n /= i;
				}
			}
		}
		if (n > 1) {
			res -= res / n;
		}
		return res;
	}

private static long Euler_pow(long a, long b) {
		long ans = 1;
		while (b > 0) {
			if ((b & 1) > 0) {
				ans = ((ans % mod) * (a % mod)) % mod;
			}
			a = ((a % mod) * (a % mod)) % mod;
			b /= 2;
		}
		return ans;
	}
}

```

0.0分

2 人评分

本文分类：题解列表
浏览次数：1370 次浏览
发布日期：2023-04-19 10:25:01
本文链接：https://blog.dotcpp.com/a/95965

上一篇 > 找规律（标题不能太短，不能太短）
下一篇 > 1044：三个字符串的排序

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

解释清晰，通俗易懂。一步一个脚印带着大家完成

评论列表共有 4 条评论

发表评论取消回复

解释清晰，通俗易懂。一步一个脚印带着大家完成

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 4 条评论

发表评论 取消回复

评论列表共有 4 条评论

发表评论取消回复