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

NYOJ 102 次方求模

編輯:C++入門知識

NYOJ 102 次方求模


次方求模

時間限制:1000 ms | 內存限制:65535 KB 難度:3
描述

求a的b次方對c取余的值

輸入
第一行輸入一個整數n表示測試數據的組數(n<100)
每組測試只有一行,其中有三個正整數a,b,c(1=
輸出
輸出a的b次方對c取余之後的結果
樣例輸入
3
2 3 5
3 100 10
11 12345 12345
樣例輸出
3
1
10481

算法分析:

大數問題,需要利用快速冪取模算法


所謂的快速冪,實際上是快速冪取模的縮寫,簡單的說,就是快速的求一個冪式的模(余)。在程序設計過程中,經常要去求一些大數對於某個數的余數,為了得到更快、計算范圍更大的算法,產生了快速冪取模算法。求a^b mod c = 幾。 (result就是取余後的結果)
算法1.普通算法:

int pow( int a, int b )
{
    int r = 1;
    while( b-- )
        r *= a;
    return r;
}
result=r%c;

這個算法的時間復雜度體現在while循環中,為O(b).這個算法存在著明顯的問題,如果a和b過大,很容易就會溢出。

算法2.二分法

int pow( int a, int b )
{
    int r = 1, base = a;
    while( b != 0 )
    {
        if( b % 2 )
            r *= base;
        base *= base;
        b /= 2;
    }
    return r;
}
result=r%c;

算法三:快速冪取模算法

首先要了解這樣一個公式:a^b mod c=(a mod c)^b mod c(詳細證明請看數論或者離散數學)
了解了這個公式,我們可以先讓a關於c取余,這樣可以大大減少a的大小, 於是不用思考的進行了改進,代碼如下:

int pow(int a, int b)
{
	int r = 1; 
	a = a % c;               //加上這一句 
	while(b--) { 
		r*=a;            //為了使r每次的數值更小,保證數據大小的可行性,這裡可以改為  r=(r*a)%c;
	}
}
result = r % c; 

這個算法在時間復雜度上沒有改進,仍為O(b),不過已經允許更大b值,但是在c過大的條件下,還是很有可能超時,所以,我們結合前面推出更快更好快速冪算法。 快速冪算法依賴於以下明顯的公式,我就不證明了。

\


我們可以看到,我們把時間復雜度變成了O(b/2).當然,這樣子治標不治本。但我們可以看到,當我們令k = (a * a) mod c時,狀態已經發生了變化,我們所要求的最終結果即為(k)b/2 mod c而不是原來的ab mod c,所以我們發現這個過程是可以迭代下去的。當然,對於奇數的情形會多出一項a mod c,所以為了完成迭代,當b是奇數時,我們通過 ans = (ans * a) % c;來彌補多出來的這一項,此時剩余的部分就可以進行迭代了。
形如上式的迭代下去後,當b=0時,所有的因子都已經相乘,算法結束。於是便可以在O(log b)的時間內完成了。於是,有了最終的算法:快速冪算法。 代碼如下:

int Pow(int a, int b, int c) 
{ 
	int r = 1; a = a % c; 
	while(b>0) 
	{ 
		
		if(b % 2 = = 1) 
			r = (r * a) % c;
		b = b/2; 
		a = (a * a) % c; 
	} 
	return r;
}

利用位操作實現快速冪的代碼如下:(測試了下這種求冪法能力很有限,如果不在中間取模,,很容易就溢出了)

#include
#include
_int64 pow( _int64 a, _int64 b );
int main()
{
	_int64 a,b,c;
	int n;
	scanf("%d",&n);
	printf("%d\n",100&1);
	while(n--){
		scanf("%I64d%I64d%I64d",&a,&b,&c);
		printf("%I64d\n",pow(a,b)%c);
	}
	return 0;
}
_int64 pow( _int64 a, _int64 b )
{
    _int64 r = 1, base = a;
	printf("%I64d  %I64d\n",a,b);
    while( b != 0 )
    {
        if( b & 1 )
            r *= base;
        base *= base;
	printf("  %I64d  %I64d\n",r,b);
        b >>= 1;
    }
    return r;
}

本題代碼如下:

#include
#include
long long pow(long long a,long long b,long long c);
int main(void)
{
	long long a,b,c;
	int n;
	scanf("%d",&n);
	while(n--){
		scanf("%lld%lld%lld",&a,&b,&c);
		printf("%lld\n",pow(a,b,c));
	}
	return 0;
}
long long pow(long long a,long long b,long long c)
{
	int r=1;
	a=a%c;
	while(b>0){
		if(b%2==1)
			r=(r*a)%c;
		b=b/2;
		a=(a*a)%c;
	}
	return r;
}

本算法的時間復雜度為O(logb),能在幾乎所有的程序設計(競賽)過程中通過,是目前最常用的算法之一,值得推廣學習!!!

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