首页 > ACM题库 > HDU-杭电 > HDU 3524-Perfect Squares[解题报告]HOJ
2014
11-05

HDU 3524-Perfect Squares[解题报告]HOJ

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;
}