HDU2837 Calculation 指数循环节欧拉函数+快速幂

13-12-10 来源：[db:作者]

收藏我要投稿

快期末了要复习，但是做数论需要时间来累积，所以保持每天做做题目

依旧是这个公式的应用，关于 A^x = A^(x % Phi(C) + Phi(C)) (mod C) 的若干证明】【指数循环节】

对于求指数循环节基本都会用到这个公式，或者求一个 A^B （B非常非常大的时候也要用到这个公式），但是要注意的是这里的X要较大才可以用这个公式，所以在快速幂取模的时候要注意区分 x是否较大

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define eps 1e-8

#define inf 0xfffffff
const ll INF = 1ll<<61;

using namespace std;

//vector<> > G;
//typedef pair P;
//vector<>> ::iterator iter;
//
//mapmp;
//map::iterator p;
//

const int N=30010;
ll prime[N];
bool isprime[N];
ll cnt;

void init()//这段求出了N内的所有素数
{
	ll i,j;
	for(i=2;i<=N;i++)
	{
		if(!isprime[i])
			prime[cnt++]=i;
		for(j=0;j1)
		ans=ans/tempn*(tempn-1);
	return ans;
}

ll quick(ll a,ll b,ll m)
{
	ll ans=1;
	ll now=1;
	for(int i=0;i= m)
			break;
	}
	if(now >= m)
		now=m;
	else
		now=0;
	while(b)
	{
		if(b&1)
		{
			ans=(ans*a)%m;
			b--;
		}
		b>>=1;
		a=a*a%m;
	}
	return ans+now;
}

ll dfs(ll n,ll m)//递归求解
{
	if(n==0)
		return 1;
	ll tmp=euler(m);
	ll p=dfs(n/10,tmp);
	ll ans=quick(n%10,p,m);
	return ans;
}

int main(void)
{
	init();
	int t;
	ll n,m;
	scanf(%d,&t);
	while(t--)
	{
		scanf(%I64d %I64d,&n,&m);
		ll ans=dfs(n,m);
		printf(%I64d
,ans%m);
	}
}

/*
2
24 20
25 20

*/

点击复制链接与好友分享!回本站首页

HDU2837 Calculation 指数循环节 欧拉函数+快速幂

HDU2837 Calculation 指数循环节欧拉函数+快速幂