Not again T-Ray
All submissions for this problem are available.
Deadpool’s arch enemy T-Ray would leave the New York city if Deadpool defeats him in a game, despite of it being a rather unconventional way for a superhero to beat his enemy. Deadpool would win the game if he could accurately predict the maximum number of times a move is made.
The game consists of two random arrays namely A and B each having the same number of elements. A move in a game is described as follows :
“In one move Deadpool can remove a pair (Ai , Bj) from the array iff they are not coprimes.”
Later, it was found that Deadpool was successfully able to predict the moves. Now, had you been in Deadpool’s place, what could have been the maximum number of moves ?
The first line contains an integer n. Two lines follow, each line containing n numbers separated by a single space.
The maximum number of times the above operation can be made.
- 0 ≤ n ≤ 10^5
- 2 ≤ A[i],B[i] ≤ 10^9
Input: 4 2 5 6 7 4 9 10 12 Output: 3
Problem Setter : Sumit Bansal
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.