求a^b%c，(1 <= a,b <= 2^62, 1 <= c <= 10^9)

最主要的高速冪

_LL mod_exp(_LL a, _LL b, int c)
{
    _LL ans = 1;
    _LL t = a%c;

    while(b)
    {
        if(b&1)
            ans = ans*t%c;
        t = t*t%c;
        b >>= 1;
    }
    return ans;
}

求a^b%c，(1 <= a,b,c <= 2^62)

由于c在long long范圍內，中間兩個long long 相乘的時候會超long long。所以對乘法再寫一個高速乘法的函數，將乘法變為加法，每加一次就進行取模，就不會超long long了。

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;
const int maxn = 110;

// a*b%c
LL mul_mod(LL a, LL b, LL c)
{
	LL ans = 0;
	a %= n;
	b %= n;
	while(b)
	{
		if(b&1)
		{
			ans = ans+a;
			if(ans >= c) ans -= c;
		}
		a <<= 1;
		if(a >= c)
			a -= c;
		b >>= 1;
	}
	return ans;
}
//a^b%c
LL pow_mod(LL a, LL b, LL c)
{
	LL ans = 1;
	a = a%c;
	while(b)
	{
		if(b&1)
			ans = mul_mod(ans,a,c);
		a = mul_mod(a,a,c);
		b >>= 1;
	}
	return ans;
}
int main()
{
	LL a,b,c;
	while(~scanf("%lld %lld %lld",&a,&b,&c))
	{
		LL ans = pow_mod(a,b,c);
		printf("%lld
",ans);
	}
	return 0;
}

求a^b%c (1 <= a,c <= 10^9, 1 <= b <= 10^1000000)

b相當大，高速冪超時。

有一個定理： a^b%c = a^(b%phi[c]+phi[c])%c，當中要滿足b >= phi[c]。這樣將b變為long long范圍內的數,再進行高速冪。至于這個定理為什么成立，如今明確一點。這篇講的挺具體：http://www.narutoacm.com/archives/a-pow-b-mod-m/

http://acm.fzu.edu.cn/problem.php?pid=1759

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;
const int maxn = 110;

LL a,c,cc;
char b[1000010];

LL Eular(LL num)
{
	LL res = num;
	for(int i = 2; i*i <= num; i++)
	{
		if(num%i == 0)
		{
			res -= res/i;
			while(num%i == 0)
				num /= i;
		}
	}
	if(num > 1)
		res -= res/num;
	return res;
}

bool Comper(char s[], LL num)
{
	char bit[30];
	int len2 = 0,len1;
	while(num)
	{
		bit[len2++] = num%10;
		num = num/10;
	}
	bit[len2] = '';

	len1 = strlen(s);
	if(len1 > len2)
		return true;
	else if(len1 < len2)
		return false;
	else
	{
		for(int i = 0; i < len1; i++)
		{
			if(s[i] < bit[len1-i-1])
				return false;
		}
		return true;
	}
}

//對大整數取模，一位一位的取。
LL Mod(char s[], LL num)
{
	int len = strlen(s);
	LL ans = 0;
	for(int i = 0; i < len; i++)
	{
		ans = (ans*10 + s[i]-'0')%num;
	}
	return ans;
}

LL Pow(LL a, LL b, LL c)
{
	LL ans = 1;
	a = a%c;
	while(b)
	{
		if(b&1)
			ans = ans*a%c;
		a = a*a%c;
		b >>= 1;
	}
	return ans;
}

int main()
{
	while(~scanf("%lld %s %lld",&a,b,&c))
	{
		LL phi_c = Eular(c);
		LL ans;
		if(Comper(b,phi_c)) // b >= phi[c]
		{
			cc = Mod(b,phi_c)+phi_c;
			ans = Pow(a,cc,c);
		}
		else
		{
			int len = strlen(b);
			cc = 0;
			for(int i = 0; i < len; i++)
				cc = cc*10 + b[i]-'0';
			ans = Pow(a,cc,c);
		}
		printf("%lld
",ans);
	}
	return 0;
}

總結

以上是生活随笔為你收集整理的a^b%c 的三种形式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。