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 212 |
| Sample Output Case #1: 2Case #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#define ll long long#define mod 10007using 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\n",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\n",ca,res); } return 0;}