Submission #7293

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

guard

#include<cstdio>

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

int dfs(int x)
{
	if(x>max)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=1LL*dfs(x+1)*a[x]%1000000007;

			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))%1000000007;
}

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

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