Perfect Squares
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 460 Accepted Submission(s): 256
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.
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).
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
/* HDU 3524 数学找规律 各种不同的完全平方数对2^N取模一共有多少种结果 找规律,因为MOD2^N,所以全部数字为2^N 用set存放 避免重复 借鉴别人思想: 一般来说一个递推式会和前两项或者前三项有关, 然后我就设了个方程F(n)=a*F(n-1)+b*F(n-2)+c, 然后带入三组数据,进行求解,,真的求出来了。 n= 1 2 3 4 5 ans=2 2 4 4 11 1:1 0 1 0=2 2:1 0 1 0=2 3(8):1 4 1 0 1 4 ...=3 4(16):1 4 9 0 9 4 1 0 ..==4 5(32):1 4 9 16 4 17 0 17 4 25 16.. ==7 F(n)=F(n-1)+2*F(n-2)-3。然后用矩阵乘法就行了。 F(n) 1 2 -1 ^n F(n-1) F(n-1) 1 0 0 F(n-2) 3 0 0 1 3 */ #include<iostream> #include<stdio.h> using namespace std; typedef __int64 LL; #define MOD 10007 struct matrix{ LL m[3][3]; }; matrix mat; void init() { memset(mat.m,0,sizeof(mat.m)); mat.m[0][0]=1; mat.m[0][1]=2; mat.m[0][2]=-1; mat.m[1][0]=1; mat.m[2][2]=1; } //矩阵相乘 matrix multi(matrix a,matrix b) { matrix c; int i,j,k; for(i=0;i<3;i++) for(j=0;j<3;j++) { c.m[i][j]=0; for(k=0;k<3;k++) c.m[i][j]+=(a.m[i][k]*b.m[k][j])%MOD; c.m[i][j]%=MOD; } return c; } //矩阵的幂 matrix powMat(int n) { matrix ans; int i,j; for(i=0;i<3;i++) for(j=0;j<3;j++) ans.m[i][j]=(i==j); for(;n;n>>=1) { if(n&1) ans=multi(ans,mat); mat=multi(mat,mat); } return ans; } int main() { int t,k; LL n,result; matrix ans; k=1; scanf("%d",&t); while(t--) { scanf("%I64d",&n); printf("Case #%d: ",k++); if(n<3) { printf("2\n"); continue; } init();//初始化矩阵 ans=powMat(n-2);//计算矩阵的幂 //矩阵与初始的数据相乘 result=(ans.m[0][0]*2%MOD+ans.m[0][1]*2%MOD+ans.m[0][2]*3%MOD+MOD)%MOD; printf("%I64d\n",result); } return 0; }