Adding Least Common Multiples
All submissions for this problem are available.
Given A and B, compute the sum of lcm(a, b) over all pairs of positive integers a and b such that:
(1) a<=A and b<=B.
(2) There is no integer n>1 such that n2 divides both a and b.
Give your answer modulo 230.
The first line contains the number of test cases, t (about 200). Each of the next t lines contains two space-separated integers A and B (1<=A, B<=4000000).
Print the answer to each test case on a separate line.
Input: 4 2 4 3 3 6 5 8 3 Output: 24 28 233 178
|Tags||MichaelD, hard, july10|
|Time Limit:||0.179775 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.