原题链接

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的一个简化剩余系。

1357就构成了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;
	}
}

运行结果

分析

第二次尝试代码

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

}

运行结果

补充说明

这第二次是我参考其他语言的代码转化成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;
	}
}

结果

分析