2
1
2

Case #1: 2
Case #2: 2

告訴一個數字n，求完全平方數摸2^n有多少不同的結果。沒有說完全平方數的范圍，想的話應該是循環著的，打表看一看，會發現n分奇數偶數時是有規律的。

n為奇數 2+（4^n-1)/3

n為偶數 2+2/3*(4^(n/2-1)-1)

算除法時分子很大，所以要用到逆元，求逆元的可以參看這篇 點擊打開鏈接

#include 
#include 
#include 
#include 
#include 
#include 
typedef long long ll;
const int mod=10007;

using namespace std;

ll fun(ll n,ll m)
{
    ll b=1;
    while(m)
    {
        if(m&1) b=b*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return b;
}

int main()
{
    int T;
    ll n;

    ll tmp=fun(3,mod-2);

    scanf(%d,&T);
    for(int ca=1;ca<=T;ca++)
    {
        scanf(%lld,&n);

        ll ans;
        if(n%2)
        {
            ll t=(fun(4,n/2)-1)%mod;
            ans=(2+t*tmp%mod)%mod;
        }

        else
        {
            ll t=(fun(4,n/2-1)-1)%mod;
             ans=(2+2*t*tmp%mod)%mod;
        }
        printf(Case #%d: %lld
,ca,ans);
    }
    return 0;
}