Leo的次幂运算——算法笔记

题目描述：

Leo是某个人的粉丝，所以她很喜欢7这个数字。 这天她心血来潮，想对7进行次幂运算。 Leo又是个想法独特的人，她想对7进行无数次幂运算，即计算7⁽⁷(7⁷(…7))) 即如图所示，假设图中有无数个7 但是这样很显然，得到的是一个很大的数字，所以请你把这个数字对p取模，并告诉她结果。

输入：

第一行为数字t，表示有t组数据 （t<=1000） 接下来的t行，每行给出一个数字p，表示取模的数字。(p<=1e7）

输出：

每组数据输出一行，表示7的无数次幂对p取模后的数字。

样例输入：

2 1234 5678

样例输出：

327 471

这个题首先想到的是快速幂，但奈何数据太大，快速幂也拯救不了。搜索一下有关题目，发现有一种欧拉降幂的东西可以用。至于为什么要这么用，我也不知道，反正能解决问题。这里有欧拉函数的两种求法：https://blog.csdn.net/weixin_43207025/article/details/90574851 知道了欧拉降幂这个定理后，这题就非常容易了。 欧拉降幂公式： 降幂公式中 φ() 为欧拉函数 参考代码：

#include <iostream> #include <algorithm> #include <string> #include <vector> #include <stack> #include <queue> #include <map> #include <set> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> using namespace std; #define INF 0x3f3f3f #define ll long long #define clean(arrays) memset(arrays, 0, sizeof(arrays)) //快速幂算法 ll quick_pow(ll a, ll b, ll mod) { ll base = a % mod; ll ans = 1; while (b) { if (b & 1) { ans = ans * base % mod; } base = base * base % mod; b >>= 1; } return ans; } //欧拉函数直接筛选 long long direct_phi(long long x) { long long ans = x; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { ans = ans - ans / i; // 这个对应的就是欧拉函数的通式 while(x % i == 0){ // 完全筛去 i 因子，确保下一个得到的 i 是 n 的素因子 x = x / i; } } } if (x > 1) { // 为了保证防止未除掉的素因子出现 ans = ans - ans / x; } return ans; } ll dfs(ll x) { if (x == 1) //模为 1 时，取模为 0 return 0; ll ph = direct_phi(x); return quick_pow(7, dfs(ph) + ph, x); } int main() { int t; cin >> t; while (t--) { ll a; cin >> a; cout << dfs(a) << endl; } return 0; }