LeetCode 372: 超级次方（欧拉降幂）

本文主要是介绍LeetCode 372: 超级次方（欧拉降幂），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

示例 1：

输入：a = 2, b = [3]
输出：8
示例 2：

输入：a = 2, b = [1,0]
输出：1024
示例 3：

输入：a = 1, b = [4,3,3,8,5,2]
输出：1
示例 4：

输入：a = 2147483647, b = [2,0,0]
输出：1198

提示：

1 <= a <= 2^31 - 1
1 <= b.length <= 2000
0 <= b[i] <= 9
b 不含前导 0

题目链接：https://leetcode-cn.com/problems/super-pow

思路：快速幂+欧拉降幂公式

定理： $(a\times b)\mod {m}=[(a\mod{m})\times(b\mod{m})]\mod{m}$

pow函数是快速幂，时间复杂度 $O(log_2n)$ 并且同时取模

从最低位开始计算，总的时间复杂度是 $O(\sum_{i=0}^{m-1}log_2b_i))$ m为b数组的大小；

思路代码来源官方题解

class Solution {const int MOD = 1337;int pow(int x, int n) {int res = 1;while (n) {if (n&1) {res = (long) res * x % MOD;}x = (long) x * x % MOD;n /= 2;}return res;}public:int superPow(int a, vector<int> &b) {int ans = 1;for (int i = b.size() - 1; i >= 0; --i) {ans = (long) ans * pow(a, b[i]) % MOD;a = pow(a, 10);}return ans;}
};

背景知识：欧拉函数

对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目，即 $\phi(n)$ 。

例如 φ(1)= 1（1与1本身互质）
φ(8)= 4（1， 3， 5， 7 与 8 互质）
并有以下引理，对于素数p
① φ§ = p - 1;
② φ(i * p) = p * φ(i) (i mod p == 0);
③ φ(i * p) = (p - 1) * φ(i) (i mod p != 0);

筛选法求欧拉函数值

int m[n],phi[n],p[n],nump;
//m[i]标记i是否为素数,0为素数,1不为素数;p是存放素数的数组;nump是当前素数个数;phi[i]为欧拉函数
int main()
{phi[1]=1;for (int i=2;i<=n;i++){if (!m[i])//i为素数{p[++nump]=i;//将i加入素数数组p中phi[i]=i-1;//因为i是素数,由特性得知    }    for (int j=1;j<=nump&&p[j]*i<=n;j++)  //用当前已得到的素数数组p筛,筛去p[j]*i{m[p[j]*i]=1;//可以确定i*p[j]不是素数 if (i%p[j]==0) //看p[j]是否是i的约数,因为素数p[j],等于判断i和p[j]是否互质 {phi[p[j]*i]=phi[i]*p[j]; //特性2break;}else phi[p[j]*i]=phi[i]*(p[j]-1); //互质,特性3其,p[j]-1就是phi[p[j]]   }}
}

欧拉降幂公式用于求 $a^b\mod c$

$a^b= a^{b\cdot\phi(n)} {\mod n}$ if a,n互质 gcd(a,n)=1

$a^b= a^b \mod n$ if $b < \phi(n)$

$a^b= a^{\phi(n)\cdot b+\phi(n)} \mod n$ if $b \geq \phi(n)$

题目链接：上帝与集合的正确用法 - 洛谷

求解 $2^{2^2...}\mod n$

#include<bits/stdc++.h>
#define ll long long
#define N 10000050
#define M 10000000
using namespace std;
const int Inf = 1e9;
int T, tot;
int phi[N], pri[N];
void Prepare_Phi() ///欧拉筛求欧拉函数
{phi[1] = 1;for(int i = 2; i <= M; ++i){if(!phi[i])pri[++tot] = i, phi[i] = i-1;///公式1for(int j = 1; j <= tot; ++j){if(i*pri[j] > M)break;if(!(i%pri[j])){phi[i*pri[j]] = phi[i] * pri[j];///公式2break;}elsephi[i*pri[j]] = phi[i] * (pri[j]-1);///公式3}}
}
ll qpow(ll x,ll y,ll mod) ///取余快速幂
{ll ret=1;while(y){if(y&1)ret = ret * x % mod;x = x * x % mod;y >>= 1;}return ret;
}
ll Solve(ll mod) ///对指数递归，模数因为是取欧拉函数所以递减
{if(mod == 1)return 0;return qpow(2,Solve(phi[mod])+phi[mod],mod);
}
int main()
{Prepare_Phi();scanf("%d", &T);while(T--){int p;scanf("%d", &p);printf("%lld\n",Solve(p));}return 0;
}

来源：https://blog.csdn.net/weixin_45737926/article/details/103756897?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.highlightwordscore&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7Edefault-1.highlightwordscorehttps://blog.csdn.net/weixin_45737926/article/details/103756897?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~default-1.highlightwordscore&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~default-1.highlightwordscore