Perfect Squares
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 276 Accepted Submission(s): 156
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
Source
还是暴力打表，然后规律
可以发现：（我也不知道具体证明过程）
an=4*an-1+5（n为奇数）
an=4*an-2+5（n为偶数）
上面两个式子可以推导出两个非常复杂的但是确实是正确的通项公式：
具体推导过程我就不写了，如果想知道可以给我发邮件，我的邮箱：
推导出来，第一个n为奇数的时候：
ans=2*4^n-5*(4^n-1)/3
ans=2*4^n-4*(4^n-1)/3
这里由于涉及到除法取余，所以还要把3的逆元求出来
另外的就看下我的代码吧
我的代码：
#include<stdio.h>
#include<stdlib.h>
#define mod 10007
typedef __int64 ll;
ll power(ll p,ll b)
{
ll sq=1;
while(b>0)
{
if(b%2==1)
sq=(sq%mod)*(p%mod)%mod;
p=(p%mod)*(p%mod)%mod;
b=b/2;
}
return sq%mod;
}
int main()
{
ll n,tmp,a,b,thr,t,T;
scanf("%I64d",&T);
for(t=1;t<=T;t++)
{
scanf("%I64d",&n);
thr=power(3,mod-2);
if(n==1||n==2)
{
printf("Case #%I64d: 2\n",t);
continue;
}
if(n&1)
{
n=n-2;
n=(n+1)/2;
tmp=power(4,n);
a=2*tmp%mod;
b=(5*thr%mod)*(((tmp-1)%mod+mod)%mod)%mod;
printf("Case #%I64d: %I64d\n",t,((a-b)%mod+mod)%mod);
}
else
{
n=n-2;
n=n/2;
tmp=power(4,n);
a=2*tmp%mod;
b=(4*thr%mod)*(((tmp-1)%mod+mod)%mod)%mod;
printf("Case #%I64d: %I64d\n",t,((a-b)%mod+mod)%mod);
}
}
return 0;
}