Game of Numbers
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Mr. Yagami is playing a game of numbers. He has two arrays, each of size N denoted by A1,A2...AN and B1,B2...BN.
Now, he has to make a move each minute. Let us maintain two sets S1 and S2 which are empty intially. In one move , first he'll pick a pair of indexes (i, j) such that it's already not present in S1. Also, Bj > Ai and GCD(Ai,Bj) is not 1. Further, he'll pick another pair of indices (p, q) such that it's already not present in S2. Also, Bp < Aq and GCD(Aq,Bp) is not 1. Also, GCD(Aq,Bp) should not be coprime to GCD(Ai,Bj). And, he'll add both pair of indices to S1 and S2, respectively.
Help Mr. Yagami by printing the largest number of moves he can perform.
First line contain T, the number of testcases. Each testcase consists of N in one line, followed by two lines of N space separated integers each, denoting arrays A and B, respectively.
For each testcase, print the maximum number of moves Mr. Yagami can make, in one line.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 400
- 1 ≤ Ai, Bi ≤ 109
Input: 2 4 2 5 6 14 3 4 7 10 2 2 3 5 7 Output: 3 0
Following are the possible moves denoting by (i,j) and (p,q)
1st move: (1,2) and (2,3)
2nd move: (1,4) and (2,4)
3rd move: (3,4) and (4,4)
In any possible combination not more than 3 moves are possible.
No move is possible.
|Tags||darkshadows, hard, july14, maths, maxflow|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.