SPOJ.com - Problem PAIRDIV

PAIRDIV - Pair Divisible

no tags

For two segments of integer [l1, r1] and [l2, r2]. How many pair (x, y) which l1 <= x <= r1 and l2 <= y <= r2 where x * y divisible by p.

The first line is integer p (1 <= p <= 10^9)

Second line includes l1, r1 separated by a space (1 <= l1 <= r1 <= 10^9).

Third line includes l2, r2 separated by a space (1 <= l2 <= r2 <= 10^9).

Result of problem.

Input:
2
1 4
2 6

Output:
16



	shashwat26: 2017-10-22 18:57:17 ac in one go
	:D: 2016-10-05 23:35:19 Re Blue.Mary: see my comment under PAIRDIV2 problem.
	[Rampage] Blue.Mary: 2016-03-08 16:56:30 It seems that PAIRDIV2 can't be solved by an O(sqrt(N)) algorithm.
	wisfaq: 2016-03-08 16:29:30 In the light of psetter's conduct, and because of the fact we have http://www.spoj.com/problems/PAIRDIV2/ now, it seems best to me to move this one to tutorial
	[Rampage] Blue.Mary: 2016-03-08 15:35:44 Recent days rejudging is no longer available for main contest. i.e. Problem setters CANNOT change verdicts after solution has been judged. P.S. This is NOT justification for this problem setter.
	wisfaq: 2016-03-08 12:36:51 When published first constraints were: Second line includes l1, r1 separated by a space (1 <= l1 <= r1 <= 10^5). Third line includes l2, r2 separated by a space (1 <= l2 <= r2 <= 10^5). I had an AC solution for those constraints. However, problemsetter thought it a good idea to change these constraints AFTER publication. In itself this isn't very nice to people that invested time in the first version. However, and I consider this extremely rude, he disqualified my AC solution. I did nothing wrong to get a solution disqualified. If you want you can rejudge but disqualify: NO. I consider this an insult. Last edit: 2016-03-08 14:34:09