http://acm.sgu.ru/problem.php?contest=0&problem=112
高精度题，在这道题纠结了很久，最终还是不知道为什么会WA on 2。有知道的同学麻烦告诉我一下。
就是用代码中的PrintBI函数输出就不行，一定得把高精度数先转成字符串，然后再输出字符串才AC。。
#include <iostream>
#include <string>
#include <list>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef list<int> BigInt;
void PrintBI(BigInt& a);
void MulBig(BigInt& a, BigInt& b, BigInt& c) {
c.clear();
BigInt::reverse_iterator ia, ib, ic, head;
int x = 0;
head = c.rbegin();
for (ia = a.rbegin(); ia != a.rend(); ++ia) {
ic = head;
x = 0;
for (ib = b.rbegin(); ib != b.rend(); ++ib) {
if (ic == c.rend()) {
c.push_front(0);
}
x = (*ia)*(*ib)+x/10000+*ic;
*(ic++) = x%10000;
}
if (x /= 10000) {
c.push_front(x);
}
head++;
}
}
void BigPow(BigInt& a, int b, BigInt& c) {
c.clear();
BigInt d = a, tmp;
c.push_front(1);
while (b) {
if (b%2) {
MulBig(d, c, tmp);
c = tmp;
}
b = b >> 1;
MulBig(d, d, tmp);
d = tmp;
}
}
int cmp(BigInt& a, BigInt& b) {
if (a.size() > b.size()) {
return 1;
}
if (a.size() < b.size()) {
return -1;
}
BigInt::iterator it1, it2;
for (it1 = a.begin(), it2 = b.begin(); it1 != a.end(); ++it1, ++it2) {
if (*it1 > *it2) {
return 1;
}
if (*it1 < *it2) {
return -1;
}
}
return 0;
}
void Minus(BigInt a, BigInt& b, BigInt& c) {
c.clear();
BigInt::reverse_iterator ia, ib, tmp;
ia = a.rbegin();
ib = b.rbegin();
while (ia != a.rend() && ib != b.rend()) {
if (*ia<*ib) {
tmp = ia;
(*(++tmp))--;
*ia += 10000;
}
c.push_front(*(ia++)-*(ib++));
}
while (ia != a.rend()) {
if (*ia < 0) {
tmp = ia;
(*(++tmp))--;
c.push_front(*ia+10000);
} else {
c.push_front(*ia);
}
ia++;
}
while (c.begin() != c.end() && *(c.begin()) == 0) {
c.erase(c.begin());
}
}
void atobi(const char* str, BigInt& a) {
int i;
for (i = strlen(str)-1; i >= 0; i -= 4) {
int sum = 0;
if (i >= 3) {
sum += (str[i-3]-'0')*1000;
}
if (i >= 2) {
sum += (str[i-2]-'0')*100;
}
if (i >= 1) {
sum += (str[i-1]-'0')*10;
}
sum += str[i]-'0';
a.push_front(sum);
}
}
void PrintBI(BigInt& a) {
BigInt::iterator it = a.begin();
cout << *it;
for (++it; it != a.end(); ++it) {
if (*it < 1000) cout << '0';
if (*it < 100) cout << '0';
if (*it < 10) cout << '0';
cout << *it;
}
}
void BItoa(BigInt& a, char* str) {
BigInt::iterator it = a.begin();
int j = 0;
if (*it >= 1000)
str[j++]=(*it)/1000+'0';
if (*it >= 100)
str[j++] = (*it)/100%10+'0';
if (*it >= 10)
str[j++] = (*it)/10%10+'0';
str[j++] = (*it)%10+'0';
for (it++; it != a.end(); ++it) {
str[j++] = (*it)/1000+'0';
str[j++] = (*it)/100%10+'0';
str[j++] = (*it)/10%10+'0';
str[j++] = (*it)%10+'0';
}
str[j] = '\0';
}
int main(void) {
int ia, ib;
cin >> ia >> ib;
BigInt a, b, r1, r2, ans;
a.push_front(ia);
b.push_front(ib);
BigPow(a, ib, r1);
BigPow(b, ia, r2);
if (cmp(r1, r2) < 0) {
BigInt tmp;
tmp = r1;
r1 = r2;
r2 = tmp;
cout << '-';
}
Minus(r1, r2, ans);
char str[300];
BItoa(ans, str);
//PrintBI(ans);
cout << str << endl;
return 0;
}