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