【基础练习】【快速幂】codevs3500 快速幂入门题解

灰太狼 2022-08-05 02:44 133阅读 0赞

啥也不说了 这是最基础的快速幂了 手打练习一下 非递归的有点点晕 都忘光了

直接上代码

非递归

//codevs3500 快速幂 复习直接手打不编译 非递归
    //copyright by ametake
    #include
       
        
    #include
        
         
    using namespace std;
    
    int mi(long long &a,long long &b,long long &c)
    {
        long long ans=1;
        while (b>0)
        {
            if (b & 1 == 1) ans=(ans*a)%c;
            a=(a*a)%c;
            b>>=1;
        }
        cout<
         
          <
          
           >a>>b>>c;
        mi(a,b,c);
        return 0;
    }

递归版本写出来是这个样子 两种都不对 原因未知！

//codevs3500 ??? ????????? ??
    //copyright by ametake
    #include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    
    int mi(long long a,long long b,long long c)
    {
        if (b==0) return 1;
        long long x=mi(a,b/2,c);
        long long ans=(x*x)%c;
        if (b&1) ans=(ans*a)%c;
        return ans;
    }
    
    int main()
    {
    	freopen("1.txt","r",stdin);
        long long a,b,c;
        cin>>a>>b>>c;
        cout<<mi(a,b,c)<<endl;
        return 0;
    }

以及

//kuaisumidigui;
    #include<iostream>
    #include<cstdio>
    using namespace std;
    long long mi(int a,int b,int c);
    
    int main(){
    	freopen("1.txt","r",stdin);
    	int a,b,c;
    	cin>>a>>b>>c;
    	cout<<mi(a,b,c);
    	return 0;
    }
    long long mi(int a,int b,int c){
    	if (b==0) return 1;
    	long long x=mi(a,b/2,c);
    	long long ans=(x*x)%c;
    	if (b%2==1) ans=(ans*a)%c;
    	return ans;
    }

里奥同学提供了一种非常简洁明了的两行代码快速幂非递归 但是还是没有过= =不知为什么 哪位大神来看看？

#include<iostream>
    #include<cstdio>
    #include<cstdlib>
    using namespace std;
    
    long long  mi(long long a,long long b,long long c)
    {
        for(long long t = a, B = b-1; B; B >>= 1, t = (t%c) * (t%c) % c)
    	if(B&1) a = (a%c) * (t%c) % c;
        return a;
    }
    
    int main(){
    	freopen("1.txt","r",stdin);
    	long long a,b,c; 
    	cin>>a>>b>>c;
    	cout<<mi(a,b,c);
    	return 0;
    }

所以还是写非递归原始版吧···

——一曲高歌一樽酒，一人独钓一江秋。