回答編集履歴
2
修正と続き
test
CHANGED
|
@@ -30,4 +30,6 @@
|
|
|
30
30
|
|
|
31
31
|
となります。この整数x, yについての方程式は、解があるときは無数に存在するので、**一次不定方程式**と呼びます。
|
|
32
32
|
|
|
33
|
-
この
|
|
33
|
+
この方程式は、**C = 0、またはCが「AとBの最大公約数」の倍数**である時に解を持つことが知られています。
|
|
34
|
+
|
|
35
|
+
最大公約数は「ユークリッドの互除法」で求まるので、Cがそれで割り切れるか判定すればいいことになります。
|
1
補足
test
CHANGED
|
@@ -15,3 +15,19 @@
|
|
|
15
15
|
```
|
|
16
16
|
|
|
17
17
|
小文字混じりの出力になっています。
|
|
18
|
+
|
|
19
|
+
|
|
20
|
+
|
|
21
|
+
### ちなみに
|
|
22
|
+
|
|
23
|
+
今回の問題の方程式を立てると、
|
|
24
|
+
|
|
25
|
+
Ax = By + C
|
|
26
|
+
|
|
27
|
+
となり、移項すると
|
|
28
|
+
|
|
29
|
+
Ax - By = C
|
|
30
|
+
|
|
31
|
+
となります。この整数x, yについての方程式は、解があるときは無数に存在するので、**一次不定方程式**と呼びます。
|
|
32
|
+
|
|
33
|
+
この解は、**C = 0、またはCが「AとBの最大公約数」の倍数**である時に解を持つことが知られています。
|