PAIRDIV  Pair Divisible
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.
Input
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).
Output
Result of problem.
Example
Input: 2 1 4 2 6 Output: 16
hide comments
shashwat26:
20171022 18:57:17
ac in one go


:D:
20161005 23:35:19
Re Blue.Mary: see my comment under PAIRDIV2 problem. 

[Rampage] Blue.Mary:
20160308 16:56:30
It seems that PAIRDIV2 can't be solved by an O(sqrt(N)) algorithm. 

wisfaq:
20160308 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:
20160308 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.


wisfaq:
20160308 12:36:51
When published first constraints were:

Added by:  Gầy :)) 
Date:  20160307 
Time limit:  1s5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 