#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],a[i]-c[i]);
}
}
else puts("0 0");
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
593 ms |
2124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
