1006.cpp

HDOJ 5月2日 “老菜鸟杯”程序大赛标准程序+解题报告

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <cctype>

using namespace std;
typedef unsigned long long ull;
typedef  long long ll;
typedef  ull BigNum;

const double PI=acos(-1.0);
const double eps=1e-11;

#define dump(x) cerr<<#x<<" = "<<(x)<<endl;

int countbit(int n) {return (n==0)?0:1+countbit(n&(n-1));}
int lowbit(int n) {return n&(n^(n-1));}
string toString(ll v) { ostringstream sout;sout<<v;return sout.str();}
string toString(int v) { ostringstream sout;sout<<v;return sout.str();}
int Rand16(){return rand();}
int Rand32(){return rand()*rand();}
double DRand(){return (double)rand()/RAND_MAX;}
int RandRange(int f,int r){return f+(int)(DRand()*(r-f)+0.5);}


BigNum Power_Add(BigNum a,BigNum b,BigNum c) //(a*b)%c
{
	BigNum ans=0;
	while (b)
	{
		if (b&1) ans=(ans+a)%c;
		a=(a+a)%c;
		b/=2;
	}
	return ans;
}

BigNum Power_Mod(BigNum a,BigNum b,BigNum c)  //(a^b)%c
{
	BigNum ans=1;
	a=a%c;
	while (b)
	{
		if (b&1) ans=Power_Add(ans,a,c);
		a=Power_Add(a,a,c);
		b/=2;
	}
	return ans;
}


int fs[10000];
int  Calc(BigNum a,BigNum b,int c) //F[a^b]%c
{
	if (c==1) return 0;

	int len;
	fs[0]=0;
	fs[1]=1;

	for (int i=2;;i++)
	{
		fs[i]=(fs[i-1]+fs[i-2])%c;
		if (fs[i]==1 && fs[i-1]==0)
		{
			len=i-1;
			break;
		}
	}

	BigNum pos=Power_Mod(a,b,len);
	return fs[pos];
}

//since a,b>=10,F[a^b] should be very large
//so F[a^b]^n will be surely great than lenb!
int visited[500][500];
int ns[10000];
int  Calc1(int val,BigNum a,BigNum b,BigNum n,int c) //(val^(F[a^b]^N))%c
{
	if (c==1) return 0;
	if (!n) return val;

	val%=c;
	memset(visited,0,sizeof(visited));

	int i;
	int lena,lenb;

	ns[0]=1;
	for (i=1;;i++)
	{
		/* wrong
		if (ns[i]==ns[0])
		{
			len=i;
			break;
		}
		*/
		ns[i]=(ns[i-1]*val)%c;
		if (visited[ns[i]][ns[i-1]])
		{
			lena=i-visited[ns[i]][ns[i-1]];
			lenb=visited[ns[i]][ns[i-1]]-1;
			break;
		}
		visited[ns[i]][ns[i-1]]=i;
	}

	//printf("val=%d,c=%d,lena=%d,lenb=%d\n",val,c,lena,lenb);

	BigNum pos;

	/*  no necessary!
	if (isLess(a,b,n,lenb))
		pos=Power_Mod(Calc(a,b,lenb),n,lenb);
	else 
	*/

	pos=(Power_Mod(Calc(a,b,lena),n,lena)-lenb%lena+lena)%lena+lenb;

	return ns[pos];
}


int main()
{
	int t,cnt=0;
	BigNum A,B,N;
	int C;
	//freopen("D:\\in.txt","r",stdin);
	//freopen("D:\\out.txt","w",stdout);

	scanf("%d",&t);

	while (t--)
	{
		cnt++;
		cin>>A>>B>>N>>C;
		int ans=Calc1(Calc(A,B,C),A,B,N-1,C);
		cout<<"Case "<<cnt<<": "<<ans<<endl;
	}
	return 0;
}