Submission #7492

#	Time	Username	Problem	Language	Result	Execution time	Memory
7492		gs13105	경비원 (GA8_guard)	C++98	37 / 100	764 ms	1164 KiB

guard

#include <stdio.h>

bool chk[2223];
int pri[331];
int arr[2222];
bool sta[20];
bool tmp[331];
int mem[16384];
int n;

int g(int x,int y)
{
	return x?g(y%x,x):y;
}

int f(int x)
{
	if(x==n)
	{
		int s=0,i,j;
		for(i=0;i<n;i++)
			s+=sta[i];
		if(s<2)
			return 0;
		for(i=0;i<n;i++)
			if(sta[i])
				for(j=i+1;j<n;j++)
					if(sta[j]&&g(arr[i],arr[j])>1)
						return 0;
		return 1;
	}
	sta[x]=0;
	int r=f(x+1);
	sta[x]=1;
	return f(x+1)+r;
}


int main()
{
	int p=0,m=0,r=0,c,t,i,j;
	const int mod=1000000007;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&arr[i]);
	if(n<=20)
	{
		printf("%d",f(0));
		return 0;
	}
	for(i=0;i<n;i++)
		m=arr[i]>m?arr[i]:m;
	for(i=2;i<=m;i++)
	{
		if(!chk[i])
		{
			pri[p++]=i;
			for(j=i*i;j<=m;j+=i)
				chk[j]=1;
		}
	}
	c=1<<p;
	for(i=0;i<n;i++)
	{
		t=0;
		for(j=0;j<p;j++)
		{
			if(arr[i]%pri[j]==0)
				t|=1;
			t<<=1;
		}
		t>>=1;
		for(j=c-1;j>=0;j--)
		{
			if((t&j)==0)
			{
				mem[t|j]+=mem[j];
				mem[t|j]%=mod;
			}
		}
		mem[t]++;
	}
	for(i=0;i<c;i++)
	{
		r+=mem[i];
		r%=mod;
	}
	printf("%d",r-n);
	return 0;
}

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