程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU1452Happy 2004(高次冪取模+積性函數+逆元)

HDU1452Happy 2004(高次冪取模+積性函數+逆元)

編輯:C++入門知識

題目意思:2004^x的所有正因數的和(S)對29求余;輸出結果;

原題鏈接

題目解析:解析參照來源:點擊打開鏈接

因子和

6的因子是1,2,3,6; 6的因子和是s(6)=1+2+3+6=12;

20的因子是1,2,4,5,10,20; 20的因子和是s(20)=1+2+4+5+10+20=42;

2的因子是1,2; 2的因子和是s(2)=1+2=3;

3的因子是1,3; 3的因子和是s(3)=1+3=4;

4的因子和是 s(4)=1+2+4=7;

5的因子和是 s(5)=1+5=6;

s(6)=s(2)*s(3)=3*4=12;

s(20)=s(4)*s(5)=7*6=42;

這是巧合嗎?

再看 s(50)=1+2+5+10+25+50=93=3*31=s(2)*s(25),s(25)=1+5+25=31.

這在數論中叫積性函數,當gcd(a,b)=1時s(a*b)=s(a)*s(b);

如果p是素數

s(p^n)=1+p+p^2+...+p^n=(p^(n+1)-1) /(p-1) (1)

例 hdu1452 Happy2004

計算 因子和 s(2004^X) mod 29,

2004=2^2 *3 *167

s(2004^X) ) = (s(2^2X))) *(s(3^X))) * (s(167^X)))

167)=22;

s(2004^X) ) = (s(2^2X))) *(s(3^X))) * (s(22^X)))

a=s(2^2X)=(2^(2X+1)-1)//根據 (1)

b=s(3^X)= (3^(X+1)-1)/2//根據 (1)

c=s(22^X)= (22^(X+1)-1)/21//根據 (1)

%運算法則 1. (a*b) %p= ( a%p) *(b%p)

%運算法則 2. (a/b) %p= ( a *b^(-1)%p)

b^(-1)是 b的逆元素 (%p)

2的逆元素是15 ()) ,因為2*15=30 % 29=1 % 29

21的逆元素是18 ()) ,因為21*18=378% 29 =1 % 29

因此

a=(powi(2,2*x+1,29)-1)%29;

b=(powi(3,x+1,29)-1)*15 %29;

c=(powi(22,x+1,29)-1)*18 %29;

ans=(a*b)% 29*c % 29;

資料拓展: 1. 高次冪快速取模鏈接

           2.積性函數:在數論中的積性函數:對於正整數n的一個算術函數 f(n),若f(1)=1,且當a,b互質時f(ab)=f(a)f(b),在數論上就稱它為積性函數。若對於某積性函數 f(n) ,就算a, b不互質,也有f(ab)=f(a)f(b),則稱它為完全積性的。若將n表示成質因子分解式

則有

3.求逆元:

 

    在計算(a/b)%Mod時,往往需要先計算b%Mod的逆元p(b有逆元的條件是gcd(b,Mod)==1,顯然素數肯定有逆元),然後由(a*p)%Mod得結果c。這裡b的逆元p滿足(b*p)%Mod=1。先來簡單證明一下:

(a/b)%Mod=c;    (b*p)%Mod=1;    ==》   (a/b)*(b*p) %Mod=c;    ==》    (a*p)%Mod=c;

從上面可以看出結論的正確性,當然這裡b需要是a的因子。接下來就需要知道根據b和Mod,我們怎麼計算逆元p了。擴展歐幾裡德算法,大家應該都知道,就是已知a、b,求一組解(x,y)使得a*x+b*y=1。這裡求得的x即為a%b的逆元,y為b%a的逆元(想想為什麼?把方程兩邊都模上b或a看看)。調用ExtGcd(b,Mod,x,y),x即為b%Mod的逆元p。

    求b%Mod的逆元p還有另外一種方法,即p=b^(Mod-2)%Mod,因為b^(Mod-1)%Mod=1(這裡需要Mod為素數)。

錯誤分析:1:

 

if(y&1)ans*=x%29;//誤把試中ans=x*x%29 

if(y&1)ans*=x%29;//誤把試中ans=x*x%29

2.數據類型要用__int64,

 


代碼實現:


  

#include<cstdio>  
#include<cstdlib>  
using namespace std; 
typedef __int64 ll; 
ll  powmol(ll  x,ll  y)//高次冪取模的求x^ymod29  
{ 
    ll  ans=1; 
    x=x%29; 
    while(y) 
    { 
        if(y&1)ans*=x%29;//y是奇數情況的處理;  
        x=x*x%29; 
        y>>=1;//  
    } 
    return ans; 
} 
int main() 
{ 
    ll  x,a,b,c; 
    while(scanf("%I64d",&x),x) 
    { 
        a=(powmol(2,2*x+1)-1)%29; 
        b=(powmol(3,x+1)-1)*15%29; 
        c=(powmol(22,x+1)-1)*18%29; 
        printf("%I64d\n",(a*b)%29*c%29); 
    } 
    return 0; 
} 

#include<cstdio>
#include<cstdlib>
using namespace std;
typedef __int64 ll;
ll  powmol(ll  x,ll  y)//高次冪取模的求x^ymod29
{
    ll  ans=1;
    x=x%29;
    while(y)
    {
        if(y&1)ans*=x%29;//y是奇數情況的處理;
        x=x*x%29;
        y>>=1;//
    }
    return ans;
}
int main()
{
    ll  x,a,b,c;
    while(scanf("%I64d",&x),x)
    {
        a=(powmol(2,2*x+1)-1)%29;
        b=(powmol(3,x+1)-1)*15%29;
        c=(powmol(22,x+1)-1)*18%29;
        printf("%I64d\n",(a*b)%29*c%29);
    }
    return 0;
}

 

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