题解 3162: 蓝桥杯2023年第十四届省赛真题-互质数的个数 C语言

需要知道些什么？:

    1.互质数是什么：两个数如果除了1以外没有其他公因数，它们就被称为互质数，也被称为相对质数或互素数。

             具体来说，两个数的最大公因数为1时，这两个数就是互质数。

                例如：2和3是互质数，因为它们除了1以外没有其他公因数；

                         而4和6不是互质数，因为它们除了1以外还有其他公因数，比如2;

    2.欧拉函数是什么：欧拉函数（Euler's totient function）是一个数论函数，表示小于等于某个正整数 n 且与 n 互质的正整数的个数。    

             它有以下性质：

                     ●若 p 是素数，则 φ(p) = p - 1。

                     ●若 p 是素数，k 是正整数，则 φ(p^k) = p^k - p^(k-1)。

                     ●若 a 和 b 互质，则 φ(ab) = φ(a) * φ(b)。

            是不是看不大懂？我这里举几个例子吧：

                    ●如果 p 是素数，那么 φ(p) = p - 1。例如，φ(5) = 4，φ(7) = 6。

                    ●如果 p 是素数，k 是正整数，则 φ(p^k) = p^k - p^(k-1)。例如，φ(2^3) = 2^3 - 2^2 = 8 - 4 = 4。

                    ●如果 a 和 b 互质，那么 φ(ab) = φ(a) * φ(b)。例如，φ(5) = 4，φ(8) = 4，而φ(5 * 8) = φ(40) = 16。

            至于欧拉函数具体是个啥，已经有大佬纤细解释说明了，再不会就百度吧

思维方法如下：

                首先，通过快速幂算法计算出 a^b 的值，记为 ans。

                然后，利用质因数分解的思想，遍历 2 到根号 n 之间的所有数 i。

                如果 n 能整除 i（即 n % i == 0），说明 i 是 n 的一个因子。

                对于每个找到的因子 i，我们将 n 除以 i，然后不断地除以相同的 i，直到 n 不再能整除 i。

                在这个过程中，我们将 n 中所有的 i 因子都除掉，最后得到的 n 就是不包含重复质因数的数。

                对于每个找到的质因数 i，我们根据欧拉函数的性质，更新与 n 互质的数的个数 res。

                对于每个质因数 i，res = res * (1 - 1/i)。

 如何使用快速幂算法计算a^b的值，代码如下：

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

            (ans % mod)：保证当前结果 ans 不超过模数 mod。

            (a % mod)：保证当前底数 a 不超过模数 mod。

            ((ans % mod) * (a % mod))：计算当前底数的幂，并将结果保持在模数 mod 范围内。

            ((ans % mod) * (a % mod)) % mod：对底数的幂再次取模，确保结果不超出模数 mod 的范围。

                   在计算指数运算的过程中，需要对结果进行取模操作，防止在连续乘法过程中，
                   中间结果超出了所需的范围，通过不断取模来保证结果在合适的范围内进行计算

如何求互质数的个数呢？

            根据欧拉函数的性质，如果 a 和 b 互质，那么 a^b 的欧拉函数值等于 φ(a) * φ(b)。

            φ(n)的计算公式是： φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pn)

                φ(n)是将n分解为其质因数乘积后，根据质因数的性质，逐个质因数求得的乘积。

                例如:    如果n是一个质数p，则φ(n) = p - 1；

                              如果n是两个不同的质数的乘积p * q，则φ(n) = (p - 1) * (q - 1)

            但是题目中，我们并不需要直接求出φ(a)和φ(b)的具体值，而是利用欧拉函数的性质和数学特性，通过其他方法间接地计算与ab互质的数的个数

    方法如下：

#include long long mod = 998244353LL;//定义了一个模数，用于最后结果的取模运算

long long Euler(long long n) {//函数接收一个正整数 n，并返回 n 的欧拉函数值 φ(n)
    long long res = n;//res 被初始化为 n，表示初始的欧拉函数值为 n
    for (long long i = 2; i * i  1) {
        res -= res / n;
    }//如果最后 n 大于 1，说明 n 是一个大于根号 n 的质因数，对 res 进行最后一次调整
    return res;//最后返回更新后的 res，即为 n 的欧拉函数值 φ(n)
}

下面添加主函数即可：

#include long long mod = 998244353LL;////加俩'LL'确保编译器正确地将该数字解释为 long long 类型，而不是 int 或者 long 类型
int main() {
    long long a, b;//定义
    scanf("%lld %lld", &a, &b);// 用于从标准输入中读取两个长整型数 a 和 b

    long long n = Euler_pow(a, b);调用 Euler_pow 函数计算 a 的 b 次方并将结果赋值给 n
    long long res = n;////long long res = n; 初始化 res 为 n，它将用于存储最终的结果

    for (long long i = 2; i  1) {
        res = (res - res / n) % mod;
    }//如果最后 n 大于 1，说明 n 是一个大于根号 n 的质因数，对 res 进行最后一次调整
       //用来处理在质因数小于或等于根号 n 的情况下，最后可能剩下一个大于 1 的质因数。
      
    printf("%lld\n", (res + mod) % mod);//通过 printf 输出 (res + mod) % mod 的结果，即为与 ab 互质的数的个数对模数取模后的值

    return 0;
}

无注释代码:

#include <stdio.h>

long long mod = 998244353LL;

long long Euler(long long n) {
    long long res = n;
    for (long 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;
}

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

int main() {
    long long a, b;
    scanf("%lld %lld", &a, &b);

    long long n = Euler_pow(a, b);
    long long res = n;

    for (long long i = 2; i <= n / i; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
                n %= mod;
            }
            res = (res - res / i) % mod;
        }
    }

    if (n > 1) {
        res = (res - res / n) % mod;
    }

    printf("%lld\n", (res + mod) % mod);

    return 0;
}

第一次认真写文章，给个五星呗~~