2014
11-05

# Perfect Squares

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.

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).

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).

2
1
2

Case #1: 2
Case #2: 2

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
#define mod 10007
const int N = 4;
struct Mat{
int mat[N][N];
void clear()
{
memset(mat,0,sizeof(mat));
}
};

Mat mul(Mat A,Mat B)
{
Mat C;
C.clear();
int i,j,k;
for(i = 0;i < N;i++)
for(j = 0;j < N;j++)
for(k = 0;k < N;k++)
C.mat[i][j] = (C.mat[i][j]+A.mat[i][k]*B.mat[k][j])%mod;
return C;
}

Mat fastm(Mat C,int n)
{
if(n == 1)
return C;
else if(n&1)
return mul(fastm(mul(C,C),n>>1),C);
else return fastm(mul(C,C),n>>1);
}

int main()
{
int t,i,n;
Mat A;
A.clear();
A.mat[0][0] = A.mat[1][1] = 2;
A.mat[0][1] = A.mat[0][3] = A.mat[1][0] = A.mat[1][2] = 0;
A.mat[2][0] = A.mat[2][1] = A.mat[2][2] = A.mat[3][0] = A.mat[3][1] = A.mat[3][3] = 0;
A.mat[0][2] = A.mat[1][3] = A.mat[2][3] = A.mat[3][2] = 1;
int f1 = 2,f2 = 2,a = -2,b = -1,fn;
scanf("%d",&t);
for(i = 1;i <= t;i++)
{
scanf("%d",&n);
if(n == 1 || n == 2)
{
printf("Case #%d: 2\n",i);
continue;
}
Mat Ans = fastm(A,n-1);
fn = ((Ans.mat[0][0]*f1)%mod+(Ans.mat[0][1]*f2)%mod+(Ans.mat[0][2]*a+Ans.mat[0][3]*b)%mod + mod)%mod;
printf("Case #%d: %d\n",i,fn);
}
return 0;
}