給你正整數 $A, B, C$ ,請找出一組整數對 $(x, y)$ 使得 $xA+yB = C$ 。
且 $0 \leq x$ , $x$ 要越小越好!
輸入共一行,有三個整數 $A, B, C$ ,且 ($1 \leq A, B, C \leq 10^ 8$)
如果成功找到滿足需求的整數對 $(x, y)$ 則輸出共兩行,
第一行為 Y
第二行有兩個整數,分別為 $x$ $y$ 。
如果無法找到滿足需求的整數對,則輸出共一行,
第一行為 N
擴展歐幾里德
No. | Testdata Range | Score |
---|---|---|
1 | 0~17 | 99 |
2 | 18~23 | 1 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 65536 | 65536 | |
1 | 1000 | 65536 | 65536 | |
2 | 1000 | 65536 | 65536 | |
3 | 1000 | 65536 | 65536 | |
4 | 1000 | 65536 | 65536 | |
5 | 1000 | 65536 | 65536 | |
6 | 1000 | 65536 | 65536 | |
7 | 1000 | 65536 | 65536 | |
8 | 1000 | 65536 | 65536 | |
9 | 1000 | 65536 | 65536 | |
10 | 1000 | 65536 | 65536 | |
11 | 1000 | 65536 | 65536 | |
12 | 1000 | 65536 | 65536 | |
13 | 1000 | 65536 | 65536 | |
14 | 1000 | 65536 | 65536 | |
15 | 1000 | 65536 | 65536 | |
16 | 1000 | 65536 | 65536 | |
17 | 1000 | 65536 | 65536 | |
18 | 1000 | 65536 | 65536 | |
19 | 1000 | 65536 | 65536 | |
20 | 1000 | 65536 | 65536 | |
21 | 1000 | 65536 | 65536 | |
22 | 1000 | 65536 | 65536 | |
23 | 1000 | 65536 | 65536 |