Pilot's Blog
0%

2023javaA组填空题一

发表于 更新于 分类于 ， ， Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟
利用欧拉函数和快速幂求解

2023填空题真题欧拉函数与快速幂

题目描述

给定a, b，求\(1 ≤ x ＜ a^b\) 中有多少个 x 与\(a^b\) 互质。 由于答案可能很大，你只需要输出答案对 998244353 取模的结果。

输入格式

输入一行包含两个整数分别表示 a, b，用一个空格分隔。 对于 30% 的评测用例，ab ≤ 106； 对于 70% 的评测用例，a ≤ 106，b ≤ 109； 对于 100% 的评测用例，1 ≤ a ≤ 109，1 ≤ b ≤ 1018 。

输出格式

输出一行包含一个整数表示答案。

输入样例

1
2
3
4
5
样例1：
2 5

样例2：
12 7

输出样例

1
2
3
4
5
样例1：
16

样例2：
11943936

分析

欧拉函数

快速幂

所以要解决上面问题，首先要用快速幂求出临界值，然后用欧拉函数求出所有的质因数

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
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    static BigInteger MOD = new BigInteger("998244353");

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        BigInteger a = scanner.nextBigInteger();
        BigInteger b = scanner.nextBigInteger();
        BigInteger ab = quickPower(a, b.subtract(BigInteger.ONE));
        BigInteger result = eulr(a).multiply(ab).mod(MOD);
        System.out.println(result);
        scanner.close();
    }

    static BigInteger quickPower(BigInteger base, BigInteger power) {
        BigInteger ans = BigInteger.ONE;
        while (power.compareTo(BigInteger.ZERO) > 0) {
            if (power.and(BigInteger.ONE).compareTo(BigInteger.ZERO) != 0) {
                ans = ans.multiply(base).mod(MOD);	//这里提前取余是关键，否则会超时
            }
            base = base.multiply(base).mod(MOD);	//
            power = power.shiftRight(1);
        }
        return ans;
    }

    static BigInteger eulr(BigInteger n) {
        BigInteger ans = n;
        for(BigInteger i = new BigInteger("2"); i.multiply(i).compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
            if(n.mod(i).equals(BigInteger.ZERO)) {
                ans = ans.subtract(ans.divide(i));
                while(n.mod(i).equals(BigInteger.ZERO)) {
                    n = n.divide(i);
                }
            }
        }
        if(n.compareTo(BigInteger.ONE) > 0) {
            ans = ans.subtract(ans.divide(n));
        }
        return ans;
    }
}

a.compareTo(b):

如果a > b， 返回1

如果a < b, 返回-1

如果a = b, 返回0