问题描述：
你的任务是计算?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
思路：快速幂+欧拉降幂公式
定理：
pow函数是快速幂，时间复杂度并且同时取模
从最低位开始计算，总的时间复杂度是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互质的数的数目，即。
例如 φ(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]; //特性2
break;
}
else phi[p[j]*i]=phi[i]*(p[j]-1); //互质,特性3其,p[j]-1就是phi[p[j]]
}
}
}
- 欧拉降幂公式用于求
?if a,n互质 gcd(a,n)=1
? if??
?if?
题目链接：上帝与集合的正确用法 - 洛谷
求解?
#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;///公式1
for(int j = 1; j <= tot; ++j)
{
if(i*pri[j] > M)
break;
if(!(i%pri[j]))
{
phi[i*pri[j]] = phi[i] * pri[j];///公式2
break;
}
else
phi[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~default~CTRLIST~default-1.highlightwordscore&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~CTRLIST~default-1.highlightwordscore