Submission #15314

#TimeUsernameProblemLanguageResultExecution timeMemory
15314progressive로봇 심판의 님 게임 (kriii3_F)C++14
79 / 79
388 ms2108 KiB
#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) { long long x=A[i]; while(true) { bool discard=false; for(int j=0;j<N;j++) if(x%P[j]==0) discard=true; int dcnt=0; for(int k=0;k<M;k++) if(x%Q[k]==0) dcnt++; if(discard || dcnt==0) break; x--; } printf("%lld %lld\n",A[i]-cnt[i]+1,A[i]-x); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...