Perfect Squares

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 82 Accepted Submission(s): 59

Problem Description

A number x is called a perfect square if there exists an integer b satisfying x=b^2. There are many beautiful theorems about perfect squares in mathematics. Among which, Pythagoras Theorem is the most famous. It says that if the length of three sides of a right triangle is a, b and c respectively(a < b <c), then a^2 + b^2=c^2. In this problem, we also propose an interesting question about perfect squares. For a given n, we want you to calculate the number of different perfect squares mod 2^n. We call such number f(n) for brevity. For example, when n=2, the sequence of {i^2 mod 2^n} is 0, 1, 0, 1, 0……, so f(2)=2. Since f(n) may be quite large, you only need to output f(n) mod 10007.

Input

The first line contains a number T<=200, which indicates the number of test case. Then it follows T lines, each line is a positive number n(0<n<2*10^9).

Output

For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is f(x).

Sample Input

2
1
2

Sample Output

Case #1: 2
Case #2: 2

Source

2010 ACM-ICPC Multi-University Training Contest（9）——Host by HNU

Recommend

zhengfeng

/*
题意：如果给定n，存在一个是b，使得b^2=n，那么就称n为完美平方数，现在让你求，小于等于n^2的所有完美平方数mod
    2^n的和

初步思路：看输出，这种题一般都是打表推公式的
    打表结果：
        2
        2
        3
        4
        7
        12
        23
        44
        87
        172
        343
        684
        1367
        2732
        5463
        10924
        21847
        43692
        87383
        174764
    奇数项是：F[n]=F[n-1]*2-1;
    偶数项是：F[n]=F[n-1]*2-2;
#错误：这种递推项是不行的，矩阵快速幂没法实现奇偶的转变

#补充：n为偶数,f[n]=(2^(n-1)-2)/3+2; 
       n为奇数,f[n]=(2^(n-1)-1)/3+2;
    现在要做的就是解决取余问题，除的时候取膜 这个地方百度了一下
    这里用到了逆元 若，b*b1 % c == 1
                   则，b1称为b模c的乘法逆元。
                   (a/b)%c==(a*b1)%c                        
*/
#include<bits/stdc++.h>
#define ll long long
#define mod 10007
using namespace std;
/************快速幂模板****************/
ll power(ll n,ll x){
    if(x==0) return 1;
    ll t=power(n,x/2);
    t=t*t%mod;
    if(x%2==1)t=t*n%mod;
    return t;
}
/************快速幂模板****************/
int t;
ll n;
ll res=0;
int main(){
    // freopen("in.txt","r",stdin);
    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++){
        scanf("%lld",&n);
        if(n<=2){
            printf("Case #%d: 2
",ca);
            continue;
        }
        if(n&1){//如果n是奇数
            res=( ( (power(2,n-1)-1 )*power(3,mod-2))%mod+2 )%mod;
        }else{//如果n是偶数
            res=( ( (power(2,n-1)-2 )*power(3,mod-2))%mod+2 )%mod;
        }
        printf("Case #%d: %lld
",ca,res);
    }
    return 0;
}