e024: 少年πの超大數運算(1)

e024: 少年πの超大數運算(1)

題目連結:e024: 少年πの超大數運算(1)

題意:

給你兩個數n,m(0<n,m<=100000),求n^m

解法:

C++:

大數

用陣列存數字

一個整數要多存幾位(我存9位)才不會TLE

time: 8.9s

memory used: 784KB

code:

#include<iostream>


#include<iomanip>


using namespace std;


int main(){


    ios::sync_with_stdio(false);


    cin.tie(0);


    long int a,i,b;


    long long int n,m,v,s;


    while(cin>>n>>m&&n&&m){


        long long int x[55560]={0};


        v=0;


        s=1;


        x[0]=1;


        for(a=1;a<=m;a++){


            for(i=0;i<s;i++){


                x[i]=x[i]*n+v;


                v=x[i]/1000000000;


                x[i]=x[i]%1000000000;


                if(v!=0&&i+1==s)


                s++;


            }


        }


        for(b=s-1;b>=0;b--){


            if(b!=s-1)


            cout << setfill('0') << setw(9) << x[b];


            else


            cout << x[b];


        }


        cout <<'\n';


    }


 }

Python:

Python已內建大數,直接運算即可

time: 4.7s

memory used: 7.7MB

code:

import sys


while True:


 line=sys.stdin.readline()


 if not line:


  break


 a,b=map(int,line.split())


 if a==0 and b==0:


  break


 print(a**b)

據說快速冪寫法較快,但實測並沒有

time: 4.8s

memory used: 7.1MB

code:

import sys


def power(a,b):


    if b==1:


        return a


    if b&1 == 0:


        temp=power(a, b>>1)


        return temp*temp


    else:


        temp=power(a,b>>1)


        return temp*temp*a


 


for line in sys.stdin:


    nums=line.split(' ')


    a=int(nums[0])


    b=int(nums[1])


    if a==0 and b==0:


        break


    print(power(a,b))

有一個很快的寫法: Decimal模組

time: 78ms

memory used: 8MB

code:

import sys


from decimal import *


setcontext(Context(prec=500001,rounding=ROUND_HALF_DOWN))


while True:


 line=sys.stdin.readline()


 a,b=map(Decimal,line.split())


 if a==b==0: break


 print(a**b)

本人的分享到此結束

若有更好的想法或建議,請在留言區留言喔