Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

快速幂+大整数乘法

Posted by huzixuan at 2020-03-12 14:59:23 on Problem 1001
#include<iostream>
#include<string.h>
#include<cstring>
#include<string>
using namespace std;
struct Biginteger {
	int digit[10000];
	int length;
	Biginteger() {
		memset(digit, 0, sizeof(digit));
		length = 0;
	}
	Biginteger(string s) {
		length = 0;
		memset(digit, 0, sizeof(digit));
		for (int i = s.length() - 1; i >= 0; i--) {
			if (s[i] != '.') {
				digit[length++] = s[i] - '0';
			}
		}
	}
};
Biginteger bigmul(Biginteger b1, Biginteger b2) {
	Biginteger answer;
	answer.length = b1.length + b2.length;
	for (int i = 0; i < b1.length; i++) {
		for (int j = 0; j < b2.length; j++) {
			answer.digit[i + j] += b1.digit[i] * b2.digit[j];
		}
	}
	for (int i = 0; i < answer.length; i++) {
		answer.digit[i + 1] += answer.digit[i] / 10;
		answer.digit[i] %= 10;
	}
	while (answer.digit[answer.length - 1] == 0 && answer.length >= 1) {
		--answer.length;
	}
	return answer;
}
Biginteger fasemi(Biginteger b, int mi) {
	Biginteger answer("1");
	while (mi != 0) {
		if (mi % 2 == 1) {
			answer = bigmul(answer, b);
		}
		mi /= 2;
		b = bigmul(b, b);
	}
	return answer;
}
bool all0(string s) {
	for (int i = 0; i < s.length(); i++) {
		if (s[i] != '0')return false;
	}
	return true;
}
int main() {
	string s;
	int t;
	while (cin >> s >> t) {
		int dotpos = 0;
		if (s.find('.') != string::npos) {
			dotpos = s.find('.');
			dotpos = s.length() - 1 - dotpos;
			dotpos *= t;
			//cout << dotpos << endl;
			s = s.erase(s.find('.'), 1);
			if (all0(s) == true) {
				cout << "0" << endl;
				continue;
			}
			Biginteger answer = fasemi(Biginteger(s), t);
			string answerstr="";
			for (int i = 0; i < answer.length; i++) {
				answerstr += answer.digit[i] + '0';
			}
			if (answer.length < dotpos) {
				for (int i = 0; i < dotpos - answer.length; i++) {
					answerstr = answerstr + "0";
				}
				answerstr = answerstr + ".";
			}
			else {
				//cout << t << endl;
				answerstr = answerstr.substr(0, dotpos) + "." + answerstr.substr(dotpos);
			}
			int i;
			for ( i = 0; i < answerstr.length() && answerstr[i] == '0'; i++);
			if (answerstr[i] == '.')++i;
			answerstr = answerstr.substr(i);
			for (int i = answerstr.length() - 1; i >= 0; i--) {
				cout << answerstr[i];
			}
			cout << endl;
		}


	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator