首页 > ACM题库 > HDU-杭电 > HDU 3609-Up-up[解题报告]HOJ
2014
11-27

HDU 3609-Up-up[解题报告]HOJ

Up-up

问题描述 :

The Up-up of a number a by a positive integer b, denoted by a↑↑b, is recursively defined by:
a↑↑1 = a,
a↑↑(k+1) = a (a↑↑k)
Thus we have e.g. 3↑↑2 = 33 = 27, hence 3↑↑3 = 327= 7625597484987 and 3↑↑4 is roughly 103.6383346400240996*10^12
The problem is give you a pair of a and k,you must calculate a↑↑k ,the result may be large you can output the answer mod 100000000 instead

输入:

A pair of a and k .a is a positive integer and fit in __int64 and 1<=k<=200

输出:

A pair of a and k .a is a positive integer and fit in __int64 and 1<=k<=200

样例输入:

3 2
3 3

样例输出:

27
97484987

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;

const long long mod=100000000ll;
int p[10005];
bool flag[10005];
int pcnt;
void pre()
{
	pcnt=0;
	memset(flag,false,sizeof(flag));
	int i=2;
	while (i<=10000)
	{
		if (flag[i])
		{
			i++;continue;
		}
		int j=i+i;
		p[pcnt++]=i;
		while (j<=10000)
		{
			flag[j]=true;
			j+=i;
		}
		i++;
	}
}
long long phi(long long x)
{
	long long res=x;
	int t=x;
	for (int i=0;p[i]*p[i]<=x && i<pcnt;i++)
	{
		if (x%p[i]==0)
		{
			res/=p[i];
			res*=p[i]-1;
			while (x%p[i]==0) x/=p[i];
			if (x==1) break;
		}
	}
	if (x!=1)
	{
		res/=x;
		res*=x-1;
	}
	return res;
}
long long power(long long a,long long b,long long mod)
{
	a%=mod;
	long long res=1;
	while (b)
	{
		if (b&1) res=(res*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return res;
}
bool larger(long long a,int b,long long p)
{
	long long now=1;
	for (int i=1;i<=b;i++)
	{
		for (int j=1;j<=a;j++)
		{
			now=now*a;
			if (now>=p) return true;
		}
		a=now;
	}
	return false;
}
long long solve(long long a,int k,long long mod)
{
	if (k==1) return a%mod;
	long long t=phi(mod);
	long long last=solve(a,k-1,t);
	if (larger(a,k-1,t)) return power(a,last%t+t,mod);
	else return power(a,last,mod);
}
int main()
{
	pre();
	long long a;
	int k;
	while (scanf("%I64d%d",&a,&k)>0)
	{
		printf("%I64d\n",solve(a,k,mod)%mod);
	}
}

  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  3. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  4. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。