原題鏈接
https://www.dotcpp.com/oj/problem3162.html
想直接看題解的，跳轉(zhuǎn)到第三次嘗試即可。
已AC。
解析：
（1）首先大家要知道什么叫互質(zhì)：
以及它們的性質(zhì)：
歐拉函數(shù)
在數(shù)論中，對(duì)正整數(shù)n，歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。此函數(shù)以其首名研究者歐拉命名，它又稱為φ函數(shù)（由高斯所命名）或是歐拉總計(jì)函數(shù)（totient function，由西爾維斯特所命名）。
例如φ(8) = 4，因?yàn)?,3,5,7均和8互質(zhì)。
也可以從簡化剩余系的角度來解釋，簡化剩余系(reduced residue system)也稱既約剩余系或縮系，是m的完全剩余系中與m互素的數(shù)構(gòu)成的子集，如果模m的一個(gè)剩余類里所有數(shù)都與m互素，就把它叫做與模m互素的剩余類。在與模m互素的全體剩余類中，從每一個(gè)類中各任取一個(gè)數(shù)作為代表組成的集合，叫做模m的一個(gè)簡化剩余系。
（1，3，5，7）就構(gòu)成了8的一個(gè)簡化剩余系。
參考鏈接： https://zhuanlan.zhihu.com/p/151756874
第一次嘗試代碼：
package Dotcpp;
import java.io.*;
import java.util.Scanner;
public class 題目3180藍(lán)橋杯2023年第十四屆省賽真題_互質(zhì)數(shù)的個(gè)數(shù) {
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;
}
}
運(yùn)行結(jié)果：
分析：
第二次嘗試代碼：
package Dotcpp;
import java.util.Scanner;
public class 題目3180藍(lán)橋杯2023年第十四屆省賽真題_互質(zhì)數(shù)的個(gè)數(shù)__運(yùn)行錯(cuò)誤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;
}
}
運(yùn)行結(jié)果：
補(bǔ)充說明：
這第二次是我參考其他語言的代碼，轉(zhuǎn)化成Java來實(shí)現(xiàn)的。
如圖可見：
感謝大佬提供的思路： https://blog.dotcpp.com/a/95823文章來源：http://www.zghlxwxcb.cn/news/detail-423321.html
分析：
當(dāng)時(shí)一想，一種方法超時(shí)，一種方法會(huì)導(dǎo)致報(bào)錯(cuò)，兩者結(jié)合一起，是不是可行呢。？
第三次嘗試：
package Dotcpp;
import java.io.*;
import java.util.Scanner;
public class 題目3180藍(lán)橋杯2023年第十四屆省賽真題_互質(zhì)數(shù)的個(gè)數(shù) {
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;
}
}
結(jié)果：
文章來源地址http://www.zghlxwxcb.cn/news/detail-423321.html
分析：
到了這里，關(guān)于題目3180:藍(lán)橋杯2023年第十四屆省賽真題-互質(zhì)數(shù)的個(gè)數(shù)======及探討互質(zhì)專題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
