歐拉降冪公式

在數論中，歐拉降冪公式是一個強大的工具，用于簡化大指數模運算。公式如下：

$$?k>\phi (m)，有A^k\equiv A^{k\mathrm{mod}\phi (m)+\phi (m)}(\mathrm{mod}m)成立。$$

其中：

• $A$ 和 $m$ 是正整數
• $\phi (m)$ 是歐拉函數
• $k$ 是指數，且 $k>\phi (m)$

這個公式允許我們將非常大的指數 $k$ 降低到可計算的范圍，從而高效地計算模冪。

歐拉函數

歐拉函數 $\phi (n)$ 表示小于或等于 $n$ 的正整數中與 $n$ 互質的數的個數。例如：

• $\phi (1)=1$
• $\phi (2)=1$（因為1與2互質）
• $\phi (3)=2$（因為1和2與3互質）
• $\phi (4)=2$（因為1和3與4互質）
• 如果 $m$ 是質數，則$\phi (m)=m?1$

計算歐拉函數 $\phi (n)$ 的代碼：

int euler(int n) {int ans = n;  // 初始化結果為nfor (int i = 2; i * i <= n; ++i)  // 遍歷2到√nif (n % i == 0) {  // 如果i是n的質因數ans = ans / i * (i - 1);  // 應用公式：ans *= (1 - 1/i)while (n % i == 0)  // 除去所有i因子n /= i;}if (n > 1)  // 處理剩余的大于√n的質因數ans = ans / n * (n - 1);return ans;
}

原理基于質因數分解，歐拉函數是積性函數，即如果 $m$ 和 $n$ 互質，則 $\phi (mn)=\phi (m)?\phi (n)$。對于任意正整數 $m$，其歐拉函數可以通過以下公式計算：
$$\phi (m)=m\prod _{p|m}\left(1?\frac{1}{p}\right)$$
時間復雜度 $O(sqrt(n))$

例題

洛谷P12847 [藍橋杯 2025 國 A] 斐波那契數列

AC代碼：

(這里還用到了矩陣快速冪求斐波那契數列，以及斐波那契前n項和的知識)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353 - 1;long long qpow(long long a, long long b) {long long res = 1;while (b > 0) {if (b & 1)res = res * a % (MOD + 1);a = a * a % (MOD + 1);b >>= 1;}return res;
}struct Matrix { // 矩陣結構體2x2long long m[2][2];Matrix() { memset(m, 0, sizeof(m)); }
};// 矩陣乘法（優化版）
Matrix multiply(const Matrix &a, const Matrix &b) {Matrix res;for (int i = 0; i < 2; ++i) {for (int j = 0; j < 2; ++j) {for (int k = 0; k < 2; ++k) {res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;}}}return res;
}// 矩陣快速冪
Matrix matrix_pow(Matrix mat, long long power) {Matrix result;result.m[0][0] = result.m[1][1] = 1; // 單位矩陣while (power > 0) {if (power & 1) {result = multiply(mat, result);}mat = multiply(mat, mat);power >>= 1;}return result;
}// 計算斐波那契數（從F(1)=1開始）
long long fibonacci(long long n) {if (n == 0)return 0;if (n == 1 || n == 2)return 1;Matrix base;base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;Matrix result = matrix_pow(base, n - 2);return (result.m[0][0] + result.m[0][1]) % MOD;;
}int main() {long long n;cin >> n;if (n == 1) {cout << 2 << endl;} else if (n == 2) {cout << 6 << endl;} else {/*斐波那契數列的前n項和:S(n) = F(n+2)-1*/int p2 = (1 + fibonacci(n - 2 + 2) - 1) % MOD + MOD;int p3 = (fibonacci(n - 1 + 2) - 1) % MOD + MOD;cout << qpow(2, p2) * qpow(3, p3) % (MOD + 1) << endl;}return 0;
}