#include<cstdio>
#include<algorithm>
using namespace std;
inline long long lcm(long long A,long long B)
{
return A*B/__gcd(A,B);
}
//!( n(p1|x v p2|x) - n(p1|x v p2|x v q1|x v q2|x))
int N,M,K;
int P[20],Q[20];
long long LCM[131072];
long long A[50];
long long cnt[50];
void calclcm()
{
for(int q=0;q<(1<<M);q++)
{
for(int i=0;i<(1<<N);i++)
{
int idx=q*(1<<N)+i;
LCM[idx]=1;
bool overflow=false;
for(int j=0;j<N;j++)
{
if(i&(1<<j)) LCM[idx]=lcm(LCM[idx],P[j]);
if(LCM[idx]>1000000000000LL)
{
LCM[idx]=-1;
overflow=true;
break;
}
}
if(overflow) continue;
for(int j=0;j<M;j++)
{
if(q&(1<<j)) LCM[idx]=lcm(LCM[idx],Q[j]);
if(LCM[idx]>1000000000000LL)
{
LCM[idx]=-1;
overflow=true;
break;
}
}
}
}
}
long long count(long long A)
{
long long cnt=0;
for(int i=0;i<(1<<N);i++)
{
if(LCM[i]==-1LL) continue;
int parity=0;
for(int j=0;j<N;j++)
if(i&(1<<j))
parity++;
if(parity%2==0) cnt+=A/LCM[i];
else cnt-=A/LCM[i];
}
for(int i=0;i<(1<<N);i++)
{
for(int q=0;q<(1<<M);q++)
{
if(LCM[i+q*(1<<N)]==-1LL) continue;
int parity=1;
for(int j=0;j<N;j++)
if(i&(1<<j))
parity++;
for(int j=0;j<M;j++)
if(q&(1<<j))
parity++;
if(parity%2==0) cnt+=A/(LCM[i+q*(1<<N)]);
else cnt-=A/(LCM[i+q*(1<<N)]);
}
}
return cnt;
}
int main()
{
scanf("%d%d%d",&N,&M,&K);
for(int i=0;i<N;i++) scanf("%d",P+i);
for(int i=0;i<M;i++) scanf("%d",Q+i);
calclcm();
for(int i=0;i<K;i++)
{
scanf("%lld",A+i);
cnt[i]=count(A[i]);
//printf("%lld: %lld\n",A[i],cnt[i]);
}
long long grundy=0;
for(int i=0;i<K;i++)
{
bool discard=false;
for(int j=0;j<N;j++)
if(A[i]%P[j]==0) discard=true;
int dcnt=0;
for(int k=0;k<M;k++)
if(A[i]%Q[k]==0) dcnt++;
if(discard || dcnt==0) continue;
grundy^=cnt[i];
}
//fprintf(stderr,"%lld",grundy);
if(grundy==0LL)
{
for(int i=0;i<K;i++)
puts("0 0");
return 0;
}
for(int i=0;i<K;i++)
{
bool discard=false;
for(int j=0;j<N;j++)
{
if(A[i]%P[j]==0)
discard=true;
}
int dcnt=0;
for(int k=0;k<M;k++)
{
if(A[i]%Q[k]==0) dcnt++;
}
long long grundytomake=grundy^cnt[i];
if(discard || dcnt==0 || cnt[i]<=grundytomake)
{
puts("0 0");
continue;
}
if(grundytomake==0LL)
{//find max cnt[i]-1
long long lo=0; // <cnt[i]
long long hi=A[i]; //>=cnt[i]
while(lo+1!=hi)
{
long long mi=(lo+hi)/2;
if(count(mi)<cnt[i]) lo=mi;
else hi=mi;
}
printf("%lld %lld\n",A[i]-cnt[i]+1,A[i]-lo);
continue;
}
else
{//find min grundytomake
long long lo=0;// <grundytomake
long long hi=A[i]; //>=grundytomake
while(lo+1!=hi)
{
long long mi=(lo+hi)/2;
if(count(mi)<grundytomake) lo=mi;
else hi=mi;
}
printf("%lld %lld\n",1LL,A[i]-hi);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
254 ms |
2108 KB |
Output is correct |
| 2 |
Correct |
257 ms |
2108 KB |
Output is correct |
| 3 |
Correct |
176 ms |
2108 KB |
Output is correct |
| 4 |
Correct |
266 ms |
2108 KB |
Output is correct |
| 5 |
Correct |
357 ms |
2108 KB |
Output is correct |
| 6 |
Correct |
178 ms |
2108 KB |
Output is correct |
| 7 |
Correct |
127 ms |
2108 KB |
Output is correct |
| 8 |
Correct |
137 ms |
2108 KB |
Output is correct |
| 9 |
Correct |
158 ms |
2108 KB |
Output is correct |
| 10 |
Correct |
146 ms |
2108 KB |
Output is correct |
| 11 |
Correct |
36 ms |
2108 KB |
Output is correct |
| 12 |
Correct |
83 ms |
2108 KB |
Output is correct |
| 13 |
Incorrect |
82 ms |
2108 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
