2325.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2325 on 2006-08-21 at 13:35:45 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int N = 256;
const int L[] = { 0, 1, 0, 7, 0, 0, 0, 3, 0, 9 };

class BigInt {
public:
	int n[N], len;
	BigInt(int64);
	void operator +=(const BigInt&);
	BigInt operator +(const BigInt& b) const { BigInt r = *this; r += b; return r; }
	BigInt operator *(const BigInt&) const;
	int64 bit(int) const;
};
BigInt::BigInt(int64 bv = 0) {
	memset(n, 0, sizeof(n));
	if(bv == 0) { len = 1; return; }
	for(len = 0; bv != 0; len++, bv /= 10) n[len] = bv%10;
}
void BigInt::operator +=(const BigInt& b) {
	len >?= b.len;
	int r = 0;
	for(int i = 0; i < len; i++) {
		n[i] += r+b.n[i];
		r  = n[i]/10; n[i] %= 10;
	}
	while(r != 0) { n[len++] = r%10; r /= 10; }
}
BigInt BigInt::operator *(const BigInt& b) const {
	BigInt r; r.len = len+b.len;
	for(int i = 0; i < len; i++)
		for(int j = 0; j < b.len; j++)
			r.n[i+j] += n[i]*b.n[j];
	for(int i = 0; i < r.len; i++) {
		int m = r.n[i]/10; r.n[i] %= 10;
		if(m != 0) { r.n[i+1] += m; r.len >?= i+2; }
	}
	return r;
}
int64 BigInt::bit(int k) const {
	int64 r = 0;
	for(int i = k-1; i >= 0; i--) r = r*10+n[i];
	return r;
}

int main()
{
	int T;

	scanf("%d", &T);
	for(int t = 0; t < T; t++) {
		int64 n; scanf("%lld", &n);
		BigInt r(L[n%10]);
		int bn = 1;
		for(int64 j = 10, i = 2; j <= n; j *= 10, i++) {
			bn = i;
			for(int k = 0; k < 10; k++) {
				BigInt tmp = r+BigInt((int64)k*j);
				if((tmp*tmp*tmp).bit(i) == n%(j*10)) 
					{ r = tmp; break; }
			}
		}
		printf("%lld\n", r.bit(bn));
	}
	
	return 0;
}