标签： URAL
题目大意
一只鹰的智商精确等于它的头的数目， 而一群鹰的智商等于各只鹰的智商的乘积。问给定一群鹰的总头数n，求这群赢的智商的最大值。
思路
求余，再乘上 n剩下的部分 分割成3的幂积（指数和底数都能相对较大）
然后如果余数小于等于1的话，就再加上三，当第一个基数大一点（这样和三比较接近）。
代码
python 比较简洁，但是效率一般
# Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
# original from http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27826
import sys
num = sys.stdin.readline()
n = int(num)
result = n % 3
n -= result
if (result <= 1 and n > 1):
result += 3
n -= 3
while n:
result *= 3
n -= 3
print result
c++ 使用高精度，效率能高一点
// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// original from http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=27826
#include <cstdio>
#define MAX_SIZE 3000
#define MOD 100000000
int answer[MAX_SIZE + 1] = { 0 };
int highest = 0; // the index to find the most significant element
void multiply3() {
int carry = 0;
for (int i = 0; i <= highest; i++) {
int remain = (answer[i] * 3 + carry) % MOD;
carry = (answer[i] * 3 + carry) / MOD;
answer[i] = remain;
if (i == highest && carry) highest++;
}
}
void output() {
printf("%d", answer[highest]);
for (int i = highest - 1; i >= 0; i--) printf("%08d", answer[i]);
printf("\n");
}
int main() {
int N;
scanf("%d", &N);
answer[0] = N % 3;
N -= answer[0];
if (answer[0] <= 1 && N >= 3) {
answer[0] += 3;
N -= 3;
}
while (N) {
multiply3();
N -= 3;
}
output();
return 0;
}
