题目3180:蓝桥杯2023年第十四届省赛真题-互质数的个数======及探讨互质专题_互质数的个数 蓝桥杯

原题链接

https://www.dotcpp.com/oj/problem3162.html

想直接看题解的，跳转到第三次尝试即可。

已AC。

解析：

（1）首先大家要知道什么叫互质：

以及它们的性质：

欧拉函数

在数论中，对正整数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

第一次尝试代码：

package Dotcpp;

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

public class 题目3180蓝桥杯2023年第十四届省赛真题_互质数的个数 {
	private static long mod = 998244353L;
	private static long a,b,ans;


	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	static StreamTokenizer st = new StreamTokenizer(br);

	static int nextLong() throws Exception {st.nextToken();return (int) st.nval;}

	static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));


	public static void main(String[] args) throws Exception {
		//Scanner scanner = new Scanner(System.in);
		a = nextLong();
		b = nextLong();
		long n = Euler_pow(a,b-1);
		long m = Euler(a);
		System.out.println((n*m%mod)%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 % 2 ==1){
				ans*=(a%mod)%mod;
			}
			a*=a%mod;
			a=a%mod;
			b /= 2;
		}
		return ans;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

运行结果：

分析：

第二次尝试代码：

package Dotcpp;

import java.util.Scanner;

public class 题目3180蓝桥杯2023年第十四届省赛真题_互质数的个数__运行错误32分 {
	private static long mod = 998244353L;
	private static long a, b, res;

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		a = scanner.nextInt();
		b = scanner.nextInt();
		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;
		}
		System.out.println(res%=mod);

	}

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

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

运行结果：

补充说明：

这第二次是我参考其他语言的代码，转化成Java来实现的。

如图可见：

感谢大佬提供的思路： https://blog.dotcpp.com/a/95823

分析：

当时一想，一种方法超时，一种方法会导致报错，两者结合一起，是不是可行呢。？

第三次尝试：

package Dotcpp;

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

public class 题目3180蓝桥杯2023年第十四届省赛真题_互质数的个数 {
	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;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

结果：

分析：