Submit

Status

Ranklist

Back to Problems List

User's AC Ratio

80.0% (12/15)

Submission's AC Ratio

31.2% (15/48)

Description

給你正整數 $A, B, C$ ，請找出一組整數對 $(x, y)$ 使得 $xA+yB = C$ 。

且 $0 \leq x$ ， $x$ 要越小越好！

Input Format

輸入共一行，有三個整數 $A, B, C$ ，且 ($1 \leq A, B, C \leq 10^ 8$)

Output Format

如果成功找到滿足需求的整數對 $(x, y)$ 則輸出共兩行，
第一行為 Y
第二行有兩個整數，分別為 $x$ $y$ 。

如果無法找到滿足需求的整數對，則輸出共一行，
第一行為 N

Sample Input 1

1 2 3

Sample Output 1

Y
1 1

Sample Input 2

4 6 2

Sample Output 2

Y
2 -1

Sample Input 3

8 6 11

Sample Output 3

Sample Input 4

3000 43 36

Sample Output 4

Y
5 -348

Sample Input 5

43 3000 36

Sample Output 5

Y
2652 -38

Hints

擴展歐幾里德

Problem Source

Subtasks

No.	Testdata Range	Score
1	0~17	99
2	18~23	1

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	1000	65536	65536	1
1	1000	65536	65536	1
2	1000	65536	65536	1
3	1000	65536	65536	1
4	1000	65536	65536	1
5	1000	65536	65536	1
6	1000	65536	65536	1
7	1000	65536	65536	1
8	1000	65536	65536	1
9	1000	65536	65536	1
10	1000	65536	65536	1
11	1000	65536	65536	1
12	1000	65536	65536	1
13	1000	65536	65536	1
14	1000	65536	65536	1
15	1000	65536	65536	1
16	1000	65536	65536	1
17	1000	65536	65536	1
18	1000	65536	65536	2
19	1000	65536	65536	2
20	1000	65536	65536	2
21	1000	65536	65536	2
22	1000	65536	65536	2
23	1000	65536	65536	2