HDU 1979 Fill the blanks

KIDx的解题报告

 

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1979

 

题意：

打表可知只有200+个4位逆素数，然后枚举四个4位逆素数然后暴力检验一下，我的剪枝可能不够直接超时了T-T，打个表存在数组中处理下即可，下面是我的超时代码（只能用来打表了）：

 

#include <iostream>
using namespace std;
#define M 10000

int p[1300], vis[M], has[M];

int cal (int i, int j, int a, int b, int tp)
{
	return p[i]/tp%10*1000 + p[j]/tp%10*100 + p[a]/tp%10*10 + p[b]/tp%10;
}

int main()
{
	//freopen ("test.txt", "w", stdout);
    int i, j, k = 0, a, b;
    for (i = 2; i < M; i++)
        if (!vis[i])
            for (j = i+i; j < M; j+=i)
                vis[j] = 1;
	for (i = 1000; i < M; i++)
	{
		if (!vis[i])
		{
			int tp = 0, j = i;
			while (j)
			{
				tp *= 10;
				tp += j % 10;
				j /= 10;
			}
			if (!vis[tp])        //逆过来也是素数的话就是逆素数
			{
				p[k++] = i;
				has[i] = 1;
			}
		}
	}
    //cout << k << endl; for (i = 0; i < 100; i++) cout << p[i] << endl;
	for (i = 0; i < k; i++)
	{
		int x = p[i]/10%10, y = p[i]/100%10;
		if (x % 2 == 0 || y % 2 == 0 || x == 5 || y == 5) continue;
		for (j = 0; j < k; j++)
		{
			for (a = 0; a < k; a++)
			{
				for (b = 0; b < k; b++)
				{
					x = p[b]/10%10, y = p[b]/100%10;
					if (x % 2 == 0 || y % 2 == 0 || x == 5 || y == 5) continue;
					x = cal (i, j, a, b, 1);
					if (!has[x]) continue;
					x = cal (i, j, a, b, 10);
					if (!has[x]) continue;
					x = cal (i, j, a, b, 100);
					if (!has[x]) continue;
					x = cal (i, j, a, b, 1000);
					if (!has[x]) continue;
			x = p[i]/1000%10*1000 + p[j]/100%10*100 + p[a]/10%10*10 + p[b]%10;
					if (!has[x]) continue;
			x = p[i]%10 + p[j]/10%10*10 + p[a]/100%10*100 + p[b]/1000%10*1000;
					if (!has[x]) continue;
					printf ("%d\n%d\n%d\n%d\n\n", p[i], p[j], p[a], p[b]);
				}
			}
		}
	}
    return 0;
}