タイトル45:ボードカバー

タイトルリンク:
http://acm.nyist.net/JudgeOnline/problem.php?pid=45
説明
ひとつの2^kで× 2^k(1<=k<=100)の碁盤にはちょうど一方の格子が覆われており、図1(k=2の場合)のように欠角の2が用いられる×2角格子(図2は右下角が欠けている1つ)、2 kを上書きする×2 kが上書きされていない格子は、図2の格子の総個数sを求める.k=1の場合、s=1;k=2の場合、s=5
入力
第1行mは、mグループのテストデータを表す.各テストデータのセットの最初の行には整数数kがある.
しゅつりょく
出力に必要な個数s;
サンプル入力
3 1 2 3
サンプル出力
1 5 21
アルゴリズムの考え方:
この問題は大数乗問題を考察している.f(k)=(2^(2*k)−1)/3,f(k+1)=(2^(2*(k+1))−1)/3であるため、f(k+1)=4*f(k)+1を押し出すことができる.数が大きいので、自分で大数乗アルゴリズムを書く必要があります.
大数乗アルゴリズムの考え方は簡単で、配列を使用して積を格納し、配列をループし、配列の各ビットを乗数に乗算し、積を前回の進位に加算して進位数にコピーし、現在のビットは進位数%10に更新し、進位数は10を除く商に更新する(下に整列する).
ソースコード

/*
Author：   
Date：2017.10.18
NYOJ（45）：    
*/
#include 
#include 
#include 
using namespace std;
int nums[65];
int main()
{
    int m, k, carray;
    cin >> m;
    while (m--)
    {
        cin >> k;
        carray = 0;
        memset(nums, 0, sizeof(nums));
        nums[0] = 1;
        for (int i = 1; i < k; i++)
        {
            //       1，     
            carray += nums[0] * 4 + 1;
            nums[0] = carray % 10;
            carray /= 10;
            for (int j = 1; j < 65; j++)
            {
                carray += nums[j] * 4;   //    
                nums[j] = carray % 10;  //            
                carray /= 10;           //     
            }
        }
        int k = 65;
        while (!nums[k]) k--;
        for (int i = k; i >= 0; i--)
            cout << nums[i];
        cout << endl;
    }
    return 0;
}