Submission #15302

#	Time	Username	Problem	Language	Result	Execution time	Memory
15302		gs13068	로봇 심판의 님 게임 (kriii3_F)	C++98	79 / 79	694 ms	2124 KiB

S

#include<cstdio>
#include<algorithm>

long long a[22],b[22],c[22],d[66666],s[66666];
int p[22],q[22],pn,qn;

long long gcd(long long a,long long b)
{
    return a?gcd(b%a,a):b;
}

long long lcm(long long a,long long b)
{
    long long g = gcd(a,b);
    if(std::min(a,b)/g>1000000)return 1e12+1;
    a*=b/g;
    return a<1e12+1?a:1e12+1;
}

long long togrundy(long long x)
{
    int i;
    long long r=0;
    for(i=0;i<(1<<(pn+qn));i++)if(i&((1<<qn)-1))
    {
        if(s[i]%2)r+=x/d[i];
        else r-=x/d[i];
    }
    return r;
}

long long tonumber(long long x)
{
    long long l=0,r=1e12,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(togrundy(mid)<x)l=mid+1;
        else r=mid;
    }
    return l;
}

long long tonumber2(long long x)
{
    long long l=0,r=1e12,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(mid-togrundy(mid)<x)l=mid+1;
        else r=mid;
    }
    return l;
}

int main()
{
    long long xo=0;
    int i,j,k,l,n;
    scanf("%d%d%d",&pn,&qn,&n);
    for(i=0;i<pn;i++)scanf("%d",&p[i]);
    for(i=0;i<qn;i++)scanf("%d",&q[i]);
    for(i=0;i<(1<<pn);i++)for(j=1;j<(1<<qn);j++)
    {
        d[(i<<qn)|j]=1;
        s[(i<<qn)|j]=0;
        for(k=0;k<pn;k++)if((i>>k)&1)
        {
            s[(i<<qn)|j]++;
            d[(i<<qn)|j]=lcm(d[(i<<qn)|j],p[k]);
        }
        for(l=0;l<qn;l++)if((j>>l)&1)
        {
            s[(i<<qn)|j]++;
            d[(i<<qn)|j]=lcm(d[(i<<qn)|j],q[l]);
        }
    }
    for(i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
        for(j=0;j<pn;j++)if(a[i]%p[j]==0)break;
        if(j<pn)
        {
            a[i]=0;
            continue;
        }
        for(k=0;k<qn;k++)if(a[i]%q[k]==0)break;
        if(k==qn)
        {
            a[i]=0;
            continue;
        }
        b[i]=togrundy(a[i]);
        xo^=b[i];
    }
    for(i=0;i<n;i++)
    {
        if((b[i]^xo)<b[i])
        {
            if(b[i]^xo)
            {
                c[i]=tonumber(b[i]^xo);
                printf("1 %lld\n",a[i]-c[i]);
            }
            else
            {
                c[i]=tonumber2(a[i]-b[i]);
                printf("%lld %lld\n",a[i]-b[i]+1,a[i]-c[i]);
            }
        }
        else puts("0 0");
    }
}

• Subtask 1: 28 / 28
• Subtask 2: 51 / 51