PAIRDIV2 - Pair Divisible 2
Let $C(N, a, b)$ be the number of integer pairs $(x, y)$ in $1 \le x \le a$, $1 \le y \le b$ such that $xy$ is divisible by $N$.
Given $N$, $a$ and $b$, find $C(N, a, b)$ modulo $10^{9}$.
Input
The first line contains $T$, the number of test cases.
In each of the next $T$ lines, you are given three numbers $N$, $a$ and $b$.
Output
For each test case, print $C(N, a, b)$ modulo $10^{9}$.
Constraints
$1 \le T \le 100$
$1 \le N \le 10^{18}$, $1 \le a \le 10^{18}$, $1 \le b \le 10^{18}$.
You can assume that the maximum prime factor of $N$ is less than or equal to $10^{5}$.
Example
Input
5 1 1 1 2 2 2 10 10 10 100 100 100 1 10000 100000
Output
1 3 27 520 0
hide comments
|
[Rampage] Blue.Mary:
2016-10-07 12:50:09
The last (constant) optimization is a little boring.
|
|
:D:
2016-10-06 10:25:22
Ok, sorry. I was looking through the perception of my approach and though O(sqrt(N)) is the complexity of factorization and a bottle neck for the entire program (if not for prime factor limit). Last edit: 2016-10-06 10:26:51 |
|
|
[Rampage] Blue.Mary:
2016-10-06 02:04:55
RE :D: The O(sqrt(N)) complexity of my algorithm is NOT depending on the factorization part. |
|
|
:D:
2016-10-05 23:34:39
I don't understand the issue. Factorization is not a problem here. Limit on prime factors takes care of that. I actually used very naive factorization function in an AC solution.
|
|
Min_25:
2016-03-08 17:30:41
@Blue.Mary
|
|
|
[Rampage] Blue.Mary:
2016-03-08 16:46:31
Are test cases (almost) randomly generated? Or contains (large numbers of) manually constructed ones?
|
| Added by: | Min_25 |
| Date: | 2016-03-08 |
| Time limit: | 3s-6s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 GOSU JS-MONKEY |
| Resource: | PAIRDIV |
RSS