leetcode 372. 超级次方 欧拉降幂

直接快速幂超时 因为要转二进制

typedef long long LL;class Solution {
public:vector<int> chu2(vector<int>& b){int jie = 0;for(int i=0;i<b.size();i++){int curr = jie*10 + b[i];jie = curr % 2;b[i] = curr/2;}return b;}bool iszero(vector<int>& b){for(auto i:b){if(i!=0){return false;}}return true;}string to_bin(vector<int> b){string bin = "";while(!iszero(b)){bin += b[b.size()-1]%2+'0';b = chu2(b);}for(int i=0;i < bin.size()/2;i++){swap(bin[i],bin[bin.size()-1-i]);}//cout<<"bin "<return bin;}int superPow(int a, vector<int>& b) {LL x = a;//x %= 1337;LL ans = 1;string bin = to_bin(b);int index = bin.size()-1;while(index>=0){if(bin[index]=='1'){ans = ans*x %1337;}x = (x*x)%1337;index--;}return ans;}
};

递归：
a x y z = ( a x y ) 10 ∗ a z a^{xyz} = (a^{xy})^{10}*a^{z} axyz=(axy)10∗az
计算一位的时候用快速幂 因为过程中要取模 否则超范围。

class Solution {
public:int myPow(int a,int n){int ans = 1;a%=1337;while(n){if(n&1){ans*=a;ans%=1337;}a*=a;a%=1337;n>>=1;}return ans;}int superPow(int a, vector<int>& b) {if(a==0 || a==1){return a;}else if(b.size() == 1 ){return int ( myPow(a,b[0]) )%1337 ;}else{int ba = b.back();b.pop_back();return  ( int(myPow( superPow(a,b),10)) %1337 * int(myPow(a,ba))%1337 )%1337;}}
};

欧拉降幂
a b ≡ { a b % ϕ ( p ) g c d ( a , p ) = 1 a b a 、 p 不 互 素 、 b < ϕ ( p ) m o d p a b % ϕ ( p ) + ϕ ( p ) a 、 p 不 互 素 、 b > = ϕ ( p ) a^b\equiv \left\{\begin{matrix} a^{b\%\phi (p)} & gcd(a,p) = 1 &\\ a^b& a 、p不互素 、b<\phi (p)& mod p\\ a^{b\%\phi (p)+\phi (p)} & a 、p不互素 、b>=\phi (p)& \end{matrix}\right. ab≡⎩⎨⎧​ab%ϕ(p)abab%ϕ(p)+ϕ(p)​gcd(a,p)=1a、p不互素、b<ϕ(p)a、p不互素、b>=ϕ(p)​modp​
这里用第一行就可以
模运算可以分配

class Solution {
public:int myPow(int a,int n){int ans = 1;a%=1337;while(n){if(n&1){ans*=a;ans%=1337;}a*=a;a%=1337;n>>=1;}return ans;}int superPow(int a, vector<int>& b) {int n = 0;if(b.size()==0){return 0;}for(int i=0;i<b.size();i++){n*=10;n+=b[i];n%=1140;}return myPow(a,n);}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！