1782 . 糟了, 是不定方程!

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

NTUOJ

Description

當你正在寫ACM培訓班作業HW6的時候, 電腦中毒了QQ

畫面出現奇怪的圖片把最重要的資訊遮住了!! 你也看不到範測!!!!!!

你只差這一題就滿4題了, 而且你也不會寫Tampopo Machine, 怎麼辦?

你知道被遮住的地方是一個不定方程.

幸好你記得這個方程是一個三維的整係數線性方程ax + by + cz = d, 只是忘了a, b, c, d是多少.

只要知道這個方程的三組整數解, 就算不知道a, b, c, d是多少, 也能計算有多少整數解在這三組解形成的(可能是退化的)三角形中(含邊界)!

Input Format

輸入的第一行有一個數字 N ( 0 < N < 16001 ) 表示資料的總數. 接著 N 行每行有九個整數 r1x, r1y, r1z, r2x, r2y, r2z, r3x, r3y, r3z.
這九個整數表示 (r1x, r1y, r1z), (r2x, r2y, r2z) 和 (r3x, r3y, r3z)是這個不定方程的三組整數解.

-1,000,000,000 ≤ r1x, r1y, r1z, r2x, r2y, r2z, r3x, r3y, r3z ≤ 1,000,000,000

Output Format

對每一筆輸入輸出一行. 此行有一個整數 T 代表可以由那三組解加權平均得到幾組整數解(權重不必是整數).

Sample Input 1

3
168 -296 203 315 -925 522 42 -814 551
-840 740 -58 441 37 -87 -189 111 87
987 851 -754 756 -592 174 -63 -555 435

Sample Output 1

28
59
194

Hints

不定方程可能是R3中的任何平面, 不代表和範測的平面相同.

Problem Source

原TIOJ1782 / problem setter: willyliu; source: NTUJ1468

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
Submit
Back to Top