Submission #7508

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

guard

#include <stdio.h>
 
bool chk[2223];
int pri[331];
int arr[2223];
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