HDU 3524 Perfect Squares 循环节+快速幂取模+找规律-白红宇

HDU 3524 Perfect Squares 循环节+快速幂取模+找规律

阅读量：3905 次

发布时间：2019-05-23

本文共 1974 字，大约阅读时间需要 6 分钟。

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

Sample Output

Case #1: 2

Case #2: 2

此题可以用两种解法求解：

方法一：

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       using namespace std;const int Mod=10007;typedef long long ll;int t;ll n;ll fastpow (ll a,ll b){    ll sum=1;    while (b>0)    {        if(b&1)            sum=sum*a%Mod;        a=a*a%Mod;        b>>=1;    }    return sum;}int main(){    scanf("%d",&t);    ll inv3=fastpow(3,Mod-2);    for (int i=1;i<=t;i++)    {        scanf("%lld",&n);        ll ans;        if(n&1)           ans=(fastpow(2,n-1)+5)%Mod*inv3%Mod;        else           ans=(fastpow(2,n-1)+4)%Mod*inv3%Mod;        printf("Case #%d: %lld\n",i,ans);    }    return 0;}

方法二：

用的循环节...

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       using namespace std;const int Mod=10007;typedef long long ll;int t;int n;int f[Mod+3];int main(){    f[0]=2;    f[1]=2;    for (int i=2;i

转载地址：http://baaen.baihongyu.com/

你可能感兴趣的文章