File Name：T022.cpp

好数字

Time Limit: 1000ms, Memory Limit: 10000KB , Accepted: 0, Total Submissions: 0

VIDEO1

Description

一个数字字符串是由数字0到9组成的，其中可能包含前导零。如果在偶数位置上（第1个字符位置为0）是偶数，奇数位置上是素数（2、3、5或7），则称该字符串是“好数字”。
例如，4562是好数字，因为它的偶数位置（4和6）是偶数，奇数位置（5和2）是素数。而3245不是好数字。
给定整数N，1≤N≤10^15，返回长度为N的好数字的总数。由于结果可能太大，以10^9+7为模。

Input

输入N。

Output

输出好数字的总数 mod 10^9+7。

• Sample Input 

  1

• Sample Output

  5

© 2002-2012  JDBSoft.

我的代碼

#include <stdio.h>
typedef unsigned long long ULL;

// 快速冪計算 (nNum^nExp) % nMod
ULL qPow(ULL nNum, ULL nExp, ULL nMod)
{
    ULL ans = 1;
    while (nExp)
    {
        if (nExp & 1)
        {
            ans = (nNum * ans) % nMod;
        }
        nExp >>= 1;
        nNum = (nNum * nNum) % nMod;
    }
    return ans;
}

int main()
{
    ULL N;
    scanf("%llu", &N);

    ULL nOdd = N / 2;
    ULL nEven = N - nOdd;

    // 模數
    ULL nMod = (ULL)1e9 + 7;

    // 快速冪
    ULL ansOdd = qPow(4, nOdd, nMod);        // 奇數每一位都有 2 3 5 7 四種選擇
    ULL ansEven = qPow(5, nEven, nMod);        // 偶數每一位都有 0 2 4 6 8 五種選擇
    ULL ansUlt = (ansOdd * ansEven) % nMod;

    printf("%llu", ansUlt);

    return 0;
}