【POJ 1001】Exponentiation (高精度乘法+快速幂)

BUPT2017 wintertraining(15) #6A

题意

求\(R^n\) ( 0.0 < R < 99.999 )(0 < n <= 25)

题解

将R用字符串读进来，找到小数点的位置，然后转为整数。

用高精度乘法和快速幂计算。输出时要确定一下小数点的位置。

代码

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

using namespace std;

const int base=10;

struct Num{

	int a[1000],len;

	Num(){memset(a,0,sizeof a);}

	void input(int b){

		int i;

		if(b==0)len=1;

		for(i=0;b;i++){

			a[i]=b%base;

			b/=base;

		}

		len=i;

	}

	void output()const {

		for(int i=len-1;i>=0;i--){

			printf("%d",a[i]);

		}

		puts("");

	}

	Num operator *(const Num &b)const{

		Num c;

		for(int i=0;i<len;i++)

		for(int j=0;j<b.len;j++){

			c.a[i+j]+=a[i]*b.a[j];

		}

		c.len=len+b.len-1;

		for(int i=0;i<c.len;i++){

			if(c.a[i]>=base){

				c.a[i+1]+=c.a[i]/base;

				c.a[i]%=base;

			}

		}

		if(c.a[c.len])c.len++;

		return c;

	}

};

char s[1000],ans[1000];

int d;

Num qpow(Num n,int d){

	Num ans;ans.input(1);

	while(d){

		if(d&1)ans=ans*n;

		n=n*n;

		d>>=1;

	}

	return ans;

}

int main() {

	while(cin>>s>>d){

		int i,j,b=0;

		for(i=0;s[i];i++){

			if(s[i]=='.'){j=i;}

			else b=b*10+s[i]-'0';

		}

		int l=(i-j-1)*d;

		Num c;c.input(b);

		c=qpow(c,d);

		for(i=c.len-1;i>=l;i--){

			printf("%d",c.a[i]);

		}

		for(j=0;c.a[j]==0;j++);

		if(i>j)printf(".");

		for(i=l-1;i>=j;i--)printf("%d",c.a[i]);

		puts("");

	}

	return 0;

}

巴特西

【POJ 1001】Exponentiation (高精度乘法+快速幂)

题意

题解

代码

最新文章

热门文章