次方(欧拉降幂)"/>
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
题目链接:
思路:快速幂+欧拉降幂公式
定理:
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]; //特性2break;}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;///公式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;
}
来源:=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.highlightwordscore=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
更多推荐
LeetCode 372: 超级次方(欧拉降幂)
发布评论