如何实现1^1+2^2+……20^20?

Question

求教：如何用java语言实现1^1+2^2+……20^20，要求不能用大数BigInteger；不能用Math；不能使用实型数；不能溢出；要求使用数组，每个数组元素只存放一位；使用循环控制。
有没有大佬能帮忙看一看啊……c++也可以。谢谢各位大佬！

Answer 1

每个数组元素只存放一位 是什么意思，数组的第i位存放i的i次方么，还是存放结果的第i位。
20的20次方能到27位数，已经超过了long long int能表示的最大值。
不是不能用大数据是不能用大数(BigIntenger)吧，意思就是自己实现一个？

#include <iostream>
#include <stdlib.h>

using namespace std;

#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))

class BigInt{
private:
    char *list;
    int length;
public:
    BigInt(int num);
    BigInt(string str);
    BigInt(const BigInt& t);
    ~BigInt();

    BigInt operator+(const BigInt& t);
    BigInt operator+=(const BigInt& t);
    BigInt operator*(const BigInt& t);
    BigInt operator*=(const BigInt& t);
    BigInt operator=(const BigInt& t);
    BigInt operator=(int t);

    friend ostream& operator<<(ostream& s,const BigInt& t);
}; 

BigInt::BigInt(int len = 1){
    if(len < 1)
        len = 1;
    length = len;
    list = new char[length];
    for(int i = 0; i < length; i++)
        list[i] = 0;
}

BigInt::BigInt(string str){
    length = str.length();
    list = new char[length];
    for(int i = 0; i < length; i++)
        list[i] = str[length - i - 1] - '0';
}

BigInt::BigInt(const BigInt& t){
    length = t.length;
    list = new char[length];
    for(int i = 0; i < length; i++)
        list[i] = t.list[i];
//  cout << "Copy :" << endl;
//  cout << "  From :" << t << endl;
//  cout << "  To   :" << *this << endl;
}

BigInt::~BigInt(){
//  cout << "Destroy : ";
//  cout << *this << endl;
//  system("pause"); 
    delete[] list;
}

BigInt BigInt::operator+(const BigInt& t){
    int l1 = (list[length-1] ? length : length - 1);
    int l2 = (t.list[t.length-1] ? t.length : t.length - 1);

    BigInt temp(max(l1, l2) + 1);
    for( int i = 0; i < max(l1, l2); i++){
        if( i < length )
            temp.list[i] += list[i]; 
        if( i < t.length )
            temp.list[i] += t.list[i];
        temp.list[i+1] += temp.list[i] / 10;
        temp.list[i] %= 10;
    }
    return temp;
}

BigInt BigInt::operator+=(const BigInt& t){
    *this = *this + t;
    return *this;
}

BigInt BigInt::operator*(const BigInt& t){
    int l1 = (list[length-1] ? length : length - 1);
    int l2 = (t.list[t.length-1] ? t.length : t.length - 1);
//  cout << "l " << l1 << " " << l2 << endl;
    BigInt temp(l1 + l2);

    int sum = 0;
    for(int i = 0; i < l1 + l2; i++){
        for(int j = max(0, i - l2 + 1); j < l1 && j <= i; j++){
            sum += list[j] * t.list[i - j];
        }
        temp.list[i] = (sum % 10);
//      cout << "[" << i << "] = " << sum << ", temp[" << i << "] = " << (int)temp.list[i] << endl;
        sum /= 10;
    }

    return temp;
}

BigInt BigInt::operator*=(const BigInt& t){
    *this = *this * t;
    return *this;
}

BigInt BigInt::operator=(const BigInt& t){
    delete[] list;
    length = t.length;
    list = new char[t.length];
    for(int i = 0; i < length; i++)
        list[i] = t.list[i];
}

BigInt BigInt::operator=(int t){
    int len = 0, n = t;
    while(n){
        len++;
        n/=10;
    }

    if(len<1) 
        len = 1;
    length = len;

    delete[] list;
    list = new char[length];

    for(int i = 0; i < length; i++){
        list[i] = t % 10;
        t /= 10;
    }
    return *this;
}

ostream& operator<<(ostream &out,const BigInt& t){
    int len = (t.list[t.length-1] ? t.length : t.length - 1);
    for(int i = len - 1; i >= 0; i--)
        out << (int)t.list[i];
    return out;
}

int main(){
    BigInt sum, a, b;
    for(int i = 1; i <= 20; i++ ){
        a = i, b = i;
        for( int j = 1; j < i; j++)
            a = a * b;
        cout << i << "^" << i << " = " << a << endl;
        sum += a;
    }

    cout << "sum = " << sum << endl;
}