【題解】ZeroJudge c874: 107北二1.雪花片片

題目敘述: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";
    }
}
分享本文 Share with friends