題目敘述：https://zerojudge.tw/ShowProblem?problemid=c874
解題想法：等比級數，大數計算
- 由題目範例觀察得知，N對應的等邊三角形數量為 4^(N-1)。
- 從 1 開始直到 N ，所對應的等邊三角形的總數量：1 + 4^1 + 4^2 + … + 4^(N-1) = (4^N – 1) / (4 – 1) = (4^N – 1) / 3。（等比級數）
- 大數計算：
- 4^N
- 除法
- 減法：不用做 ( 4^N 的個位數必定 >= 1，本題只做「減 1」計算。）
- N 最大為 120，4^120 = 2^240 = (2^10)^24 = 1024^24 (陣列開75就夠了。)
#include <iostream>
#include <cstring>
using namespace std;
int a[75];
void power(int b){
// 大數階乘
for (int i = 0; i < b; i++){
int carry = 0;
for (int j = 0; j < 75; j++){
a[j] = a[j] * 4 + carry;
carry = a[j] / 10;
a[j] = a[j] % 10;
}
}
}
void divide(int b){
// 大數除法
int carry = 0;
for (int i = 74; i >= 0; i--){
a[i] += carry * 10;
carry = a[i] % b;
a[i] = a[i] / b;
}
}
int main(){
int n;
while (cin >> n){
memset(a, 0, sizeof(a));
a[0] = 1;
power(n);
a[0] -= 1;
divide(3);
bool flag = false;
for (int i = 74; i >= 0; i--){
if (a[i] == 0 && !flag) continue;
flag = true;
cout << a[i];
}
cout << "\n";
}
}