程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 3524 Perfect Squares 推公式求逆元

hdu 3524 Perfect Squares 推公式求逆元

編輯:C++入門知識

hdu 3524 Perfect Squares 推公式求逆元


 

Perfect Squares

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 501 Accepted Submission(s): 272



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

 

告訴一個數字n,求完全平方數摸2^n有多少不同的結果。沒有說完全平方數的范圍,想的話應該是循環著的,打表看一看,會發現n分奇數偶數時是有規律的。

n為奇數 2+(4^n-1)/3

n為偶數 2+2/3*(4^(n/2-1)-1)

算除法時分子很大,所以要用到逆元,求逆元的可以參看這篇 點擊打開鏈接

 

 

#include 
#include 
#include 
#include 
#include 
#include 
typedef long long ll;
const int mod=10007;

using namespace std;

ll fun(ll n,ll m)
{
    ll b=1;
    while(m)
    {
        if(m&1) b=b*n%mod;
        n=n*n%mod;
        m>>=1;
    }
    return b;
}

int main()
{
    int T;
    ll n;

    ll tmp=fun(3,mod-2);

    scanf(%d,&T);
    for(int ca=1;ca<=T;ca++)
    {
        scanf(%lld,&n);

        ll ans;
        if(n%2)
        {
            ll t=(fun(4,n/2)-1)%mod;
            ans=(2+t*tmp%mod)%mod;
        }

        else
        {
            ll t=(fun(4,n/2-1)-1)%mod;
             ans=(2+2*t*tmp%mod)%mod;
        }
        printf(Case #%d: %lld
,ca,ans);
    }
    return 0;
}

 

 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved