A frequency-testing lab has a row of towers and a separate row of base emitters. Before any comparison is made, every base emitter's frequency is scaled by a fixed multiplier k. A tower is said to be in harmonic lock with a base emitter if the tower's frequency is evenly divisible by that base emitter's scaled frequency (the base emitter's raw frequency multiplied by k, with remainder zero). Every tower is compared against every base emitter independently — a single tower may lock with several base emitters, and a single base emitter may lock with several towers. Report the total number of (tower, base emitter) pairs that are in harmonic lock.
Line 1: three integers n1 n2 k — the number of towers, the number of base emitters, and the multiplier.
Line 2: n1 integers — the tower frequencies A[0..n1-1].
Line 3: n2 integers — the raw base emitter frequencies B[0..n2-1].
A single integer: the total number of (tower, base emitter) pairs (i, j) such that A[i] % (B[j] * k) == 0.
Example 1
Input
2 2 1 12 8 3 4
Expected
3
Explanation
With k=1 the scaled base frequencies are 3 and 4. Tower 12 is divisible by both 3 and 4 (2 locks). Tower 8 is divisible by 4 but not 3 (1 lock). Total = 2 + 1 = 3.
Example 2
Input
3 1 2 10 20 7 5
Expected
2
Explanation
With k=2 the single base emitter's scaled frequency is 5*2=10. Towers 10 and 20 are both divisible by 10, but 7 is not. Total = 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →