#include<cstdio>
#include<algorithm>
long long a[22],b[22],c[22];
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,j,k,l,t;
long long r=0,lc;
for(i=0;i<(1<<pn);i++)for(j=1;j<(1<<qn);j++)
{
lc=1;
t=0;
for(k=0;k<pn;k++)if((i>>k)&1)
{
if(lc>x)break;
t++;
lc=lcm(lc,p[k]);
}
for(l=0;l<qn;l++)if((j>>l)&1)
{
if(lc>x)break;
t++;
lc=lcm(lc,q[l]);
}
if(lc>x)continue;
if(t%2)r+=x/lc;
else r-=x/lc;
}
return r;
}
long long tonumber(long long x)
{
long long l=x,r=1e12,mid;
while(l<r)
{
mid=(l+r+1)/2;
if(togrundy(mid)>x)r=mid-1;
else l=mid;
}
return l;
}
int main()
{
long long xo=0;
int i,j,k,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<n;i++)
{
scanf("%lld",&a[i]);
b[i]=togrundy(a[i]);
xo^=b[i];
}
for(i=0;i<n;i++)
{
for(j=0;j<pn;j++)if(a[i]%p[j]==0)break;
if(j<pn)
{
puts("0 0");
continue;
}
for(k=0;k<qn;k++)if(a[i]%q[k]==0)break;
if(k==qn)
{
puts("0 0");
continue;
}
if((b[i]^xo)<b[i])
{
c[i]=tonumber(b[i]^xo);
printf("1 %lld\n",a[i]-c[i]);
}
else puts("0 0");
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
2000 ms |
1084 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
