| Submit | All submissions | Best solutions | Back to list |
GPINTRI - Grid Points in a Triangle |
How many points (x, y) with non-negative integer coordinates satisfy y ≤ ax / b and x ≤ n?
Input
The first line contains an integer T (T ≤ 100000). T lines follow, each contains three positive integers n, a, b, where n, a, b ≤ 109 and a ≤ b.
Output
T lines, each contains a single integer denoting to the number of points according to the description.
Example
Input:
5
8 2 10
8 4 4
7 1 5
713241932 127894722 957823358
759096725 496666160 980149020
Output:
13
45
11
33963383064794976
145994569610845896
Warning: enormous input/output data, be careful with certain languages
| Added by: | Lox |
| Date: | 2009-08-26 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
| Resource: | Own problem |
hide comments
|
2009-08-30 14:18:34 Tony Beta Lambda
I guess you do not need much math knowledge, instead you should have strong math ability. My code did use stdio.h only. Last edit: 2009-08-30 14:19:39 |
|
|
2009-08-28 02:00:56 Lox
It doesn't involve complex maths. As for the second question, it's hard to say because you have to calculate it. |
|
|
2009-08-27 08:07:28 ~ adieus ~
Does this involve very complex maths ??? what is change in number of points , if the triangle is moved h units along y axis in positive direction. (h<1) |
RSS