Problem : 22 - 駭客

Problem Statistics

Solved Member: 20　　Submission: 135　　User Tried: 28

Statement:

一位駭客正在破解國防部的訊息。他發現國防部的加密方式非常有趣，每一個文字都加密成3個正整數a,b,d所組成。解碼方式是找出(x,y)滿足以下的條件：

1 <= x <= a
1 <= y <= b
gcd(x,y) = d，gcd代表x,y的最大公因數。

解密出來的結果就是滿足上述條件的(x,y)的方法數。

他想請你寫一個程式來幫助他破解國防部發出的訊息。

Task:

你需要寫一個程式來達成以下任務：
1.讀入已加密的3個數字
2.算出未加密前的樣子
3.輸出這個數字

Input:Output:

第1行有一個整數n(1 <= n <= 50000)，代表詢問的筆數。
接下來的n行每行有3個正整數a,b,d(1 <= d <= a,b <= 50000)，以空格分開，代表每一筆詢問的數字。

你需要輸出n行，每行有1個數字，代表加密前的答案。

Sample Input:Sample Output:

2
4 5 2
6 4 3

3
2

HINT:

滿足第1筆範測的所有可能：(2,2),(2,4),(4,2)
滿足第2筆範測的所有可能：(6,3),(3,3)

Source:

POI 14 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	3000ms	32768kb
1-ocen	3000ms	32768kb
1	1000ms	32768kb	6
2-ocen	3000ms	32768kb
2	1000ms	32768kb	6
3-ocen	3000ms	32768kb
3	1000ms	32768kb	6
4-ocen	30000ms	32768kb
4	2000ms	32768kb	6
5	8000ms	32768kb	6
6	8000ms	32768kb	7
7	1000ms	32768kb	7
8	1000ms	32768kb	7
9	3000ms	32768kb	7
10	22000ms	32768kb	7
11	18000ms	32768kb	7
12	10000ms	32768kb	7
13	10000ms	32768kb	7
14	9000ms	32768kb	7
15	20000ms	32768kb	7