http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5840

Time Limit: 1 Second      Memory Limit: 65536 KB

Problem solving report:

Description: 签到题,给你一个x和一个k,根据上面的表求g^k(x),例如g^2(1234)=f(f(1234))=f(1)=0.

Problem solving: 范围是1e9,直接递归算的话会超时,我们可以发现,到了后面就是在01之间循环了,所以值到达0之后,根据还要再进行的次数的奇偶性判断即可.

#include <stdio.h>
int m[] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
int mm(int n)
{
	int ans = 0;
	if (!n)
		return 1;
	while (n)
	{
		ans += m[n % 10];
		n /= 10;
	}
	return ans;
}
int main()
{
	int t, x, k;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &x, &k);
		while (k--)
		{
			x = mm(x);
			if (!x)
				break;
		}
		if (k > 0 && k & 1)
			x = 1;
		printf("%d\n", x);
	}
	return 0;
}