Submission #7292

#	Time	Username	Problem	Language	Result	Execution time	Memory
7292		gs13068	경비원 (GA8_guard)	C++98	0 / 100	2000 ms	1104 KiB

guard

#include<cstdio>

int a[2223];
int d[2223];

int dfs(int x)
{
	if(x>2222)return 1;
	int i,t,r=0;
	if(a[x])
	{
		t=x;
		for(i=2;i*i<=t;i++)
		{
			if(t%i==0&&d[i])break;
			while(t%i==0)t/=i;
		}
		if(i*i>t&&!d[t])
		{
			t=x;
			for(i=2;i*i<=t;i++)if(t%i==0)
			{
				d[i]=1;
				while(t%i==0)t/=i;
			}
			if(t>1)d[t]=1;

			r+=dfs(x+1)*a[x];

			t=x;
			for(i=2;i*i<=t;i++)if(t%i==0)
			{
				d[i]=0;
				while(t%i==0)t/=i;
			}
			if(t>1)d[t]=0;
		}
	}
	return r+dfs(x+1);
}

int main()
{
	int i,n,t;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
	{
		scanf("%d",&t);
		a[t]++;
	}
	printf("%d",dfs(1)-n-1);
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 27
• Subtask 5: 0 / 36