/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
T 個のテストケースについて、以下の問題を解いてください。
高橋君は「ルンルンマート」で使える M 円の商品券を 10^{100} 枚持っています。
この商品券を、購入する商品の金額に比べて過剰に使った場合でも、おつりが返ってくることはありません。
高橋君は、 i 日目に A \times i 円のリンゴを商品券のみを使って買います。
このとき、 A \times i 円以上を支払える最小の (M 円の) 商品券の枚数を k 枚とすると、高橋くんの「悲しさ」が k \times M - A \times i だけ増加します。
この買い物を N 日続けたとき、高橋君の「悲しさ」の総和はいくつになりますか?
制約
- 入力は全て整数
- 1 \le T \le 10^5
- 1 \le N \le 10^6
- 1 \le A,M \le 300
入力
入力は以下の形式で標準入力から与えられる。
T
\rm{case}_1
\rm{case}_2
\dots
\rm{case}_T
ただし、 \rm{case}_i は i 番目のテストケースを表し、各テストケースは以下の形式で与えられる。
N A M
出力
計 T 行出力せよ。
i 行目に i 番目のテストケースの答えを整数として出力せよ。
入力例 1
10 4 5 8 8 9 10 4 10 7 10 1 5 6 4 9 304607 77 89 291969 231 9 424790 216 294 76881 213 111 312895 58 1
出力例 1
14 36 12 20 24 13402703 875907 61169622 4151490 0
この入力には、 10 個のテストケースが含まれています。
1 番目のケースでは、 N=4,A=5,M=8 です。
- 1 日目には 5 円のリンゴを買います。 8 円の商品券は 1 枚必要で、このとき高橋君の「悲しさ」は 3 増加します。
- 2 日目には 10 円のリンゴを買います。 8 円の商品券は 2 枚必要で、このとき高橋君の「悲しさ」は 6 増加します。
- 3 日目には 15 円のリンゴを買います。 8 円の商品券は 2 枚必要で、このとき高橋君の「悲しさ」は 1 増加します。
- 4 日目には 20 円のリンゴを買います。 8 円の商品券は 3 枚必要で、このとき高橋君の「悲しさ」は 4 増加します。
よって、 1 番目のケースに対する答えは、 3+6+1+4=14 となります。
Score : 6 points
Problem Statement
Solve the following problem for T test cases.
Takahashi has 10^{100} coupons, each worth M yen, available in Lunlun Mart.
The shop does not give change on these coupons where the price of the purchased item is less than the value of the coupons.
On the i-th day, Takahashi will buy an apple worth A \times i yen using only the coupons.
Here, the sadness of Takahashi increases by k \times M - A \times i, where k is the minimum number of (M-yen) coupons needed to pay at least A \times i yen.
In N days of shopping, how much total sadness will Takahashi accumulate?
Constraints
- All values in input are integers.
- 1 \le T \le 10^5
- 1 \le N \le 10^6
- 1 \le A,M \le 300
Input
Input is given from Standard Input in the following format:
T
\rm{case}_1
\rm{case}_2
\dots
\rm{case}_T
Here, \rm{case}_i represents the i-th test case in the following format:
N A M
Output
Print T lines.
The i-th line should contain the answer to the i-th test case as an integer.
Sample Input 1
10 4 5 8 8 9 10 4 10 7 10 1 5 6 4 9 304607 77 89 291969 231 9 424790 216 294 76881 213 111 312895 58 1
Sample Output 1
14 36 12 20 24 13402703 875907 61169622 4151490 0
This input contains 10 test cases.
In the first case, N=4, A=5, and M=8.
- On the 1-st day, he buys an apple worth 5 yen. One 8-yen coupon is needed, and his sadness increases by 3.
- On the 2-nd day, he buys an apple worth 10 yen. Two 8-yen coupons are needed, and his sadness increases by 6.
- On the 3-rd day, he buys an apple worth 15 yen. Two 8-yen coupons are needed, and his sadness increases by 1.
- On the 4-th day, he buys an apple worth 20 yen. Three 8-yen coupons are needed, and his sadness increases by 4.
Therefore, the answer to this case is 3+6+1+4=14.