2553740_ac_906ms_4084k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char k[101], tt[120];
int num[20];
int l, len;
int prime[1000001];

void init()
{
	int i, j;

	memset(prime,0,sizeof(prime));
	for(i = 2; i < 1000001; i++)
	{
		if(prime[i]==0)
		{
			for(j = 2*i; j < 1000001; j+=i)
				prime[j] = 1;
		}
	}
	int num = 0;
	for(i = 2; i < 1000001; i++)
		if(!prime[i])
			prime[num++] = i;
	prime[num] = 100000000;
}

int f(int a)
{
	int i;

	for(i = 10; ; i*=10)
		if(a==i)
			return i*10;
		else
			if(a/i==0)
				return i;
}

int div(int N)
{
	int i;
	__int64 t, n;

	t = 0;n = N;
	for(i = 0; i < len; i++)
	{
		t += num[i];
		if(t>=n)
			t %= n;
		if(i<len-2)
			t *= 1000000;
		else
			if(i==len-2)
				t *= f(num[i+1]);
	}
	return t==0;
}

void get_num()
{
	int l, t, i, j;

	t = 0;
	l = strlen(k);
	for(i = 0; i < l; i += 6)
	{
		num[t] = 0;
		for(j = i; j < i+6&&k[j]!='\0'; j++)
		{
			num[t] += k[j]-'0';
			num[t] *= 10;
		}
		num[t] /= 10;
		t++;
	}
	len = t;
}

int main()
{
	int i;

	init();
	while(scanf("%s%d",k,&l)==2)
	{
		if(!l)
			break;
		get_num();
		for(i = 0; prime[i] < l; i++)
		{
			if(div(prime[i]))
			{
				printf("BAD %d\n",prime[i]);
				goto con;
			}
		}
		printf("GOOD\n");
con:
		;
	}
	return 0;
}