| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
快速幂+大整数乘法#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator