質問編集履歴
5
意図的に削除された質問であったため元に戻しました。
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
|
|
1
|
+
剰余演算を使わずに最大公約数を求めるには
|
test
CHANGED
|
@@ -1 +1,85 @@
|
|
|
1
|
+
### 前提・実現したいこと
|
|
2
|
+
|
|
3
|
+
プログラミング超初心者で初めて質問させていただきました。
|
|
4
|
+
|
|
5
|
+
題名にもある通り剰余計算を使わずに2変数x,yの最大公約数を求めるにはどのようにすればよいですか？
|
|
6
|
+
|
|
7
|
+
最大公約数をgcd(x,y)とし、
|
|
8
|
+
|
|
9
|
+
ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)
|
|
10
|
+
|
|
11
|
+
xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
|
|
12
|
+
|
|
13
|
+
x,yどちらも奇のとき、gcd(x,y)→gcd((x,y)/2,y)
|
|
14
|
+
|
|
15
|
+
という要領で計算します。
|
|
16
|
+
|
|
17
|
+
できれば演算子％を使わずにお願いします。
|
|
18
|
+
|
|
19
|
+
ここに質問の内容を詳しく書いてください。
|
|
20
|
+
|
|
21
|
+
### 発生している問題・エラーメッセージ
|
|
22
|
+
|
|
23
|
+
```
|
|
24
|
+
|
|
25
|
+
def gcd(x, y):
|
|
26
|
+
|
|
27
|
+
if y==0:
|
|
28
|
+
|
|
29
|
+
return x
|
|
30
|
+
|
|
31
|
+
elif x&1==0 and y&1==0 and y!=0:
|
|
32
|
+
|
|
33
|
+
x, y=x//2, y//2
|
|
34
|
+
|
|
35
|
+
return 2*gcd(x, y)
|
|
36
|
+
|
|
37
|
+
elif x&1==0 and y&1==1 and y!=0:
|
|
38
|
+
|
|
39
|
+
x=x//2
|
|
40
|
+
|
|
41
|
+
return gcd(x, y)
|
|
42
|
+
|
|
43
|
+
elif x&1==1 and y&1==0 and y!=0:
|
|
44
|
+
|
|
45
|
+
y=y//2
|
|
46
|
+
|
|
47
|
+
return gcd(x, y)
|
|
48
|
+
|
|
49
|
+
elif x&1==1 and y&1==1 and x<y and y!=0:
|
|
50
|
+
|
|
51
|
+
x, y=x, (y-x)//2
|
|
52
|
+
|
|
53
|
+
return gcd(x, y)
|
|
54
|
+
|
|
55
|
+
else:
|
|
56
|
+
|
|
57
|
+
x, y=(x-y)//2, y
|
|
58
|
+
|
|
59
|
+
return gcd(x, y)
|
|
60
|
+
|
|
1
|
-
|
|
61
|
+
print(f'gcd(123456, 65432)={gcd(123456, 65432)}')
|
|
62
|
+
|
|
63
|
+
に対してエラーが出ます。
|
|
64
|
+
|
|
65
|
+
```
|
|
66
|
+
|
|
67
|
+
### 該当のソースコード
|
|
68
|
+
|
|
69
|
+
```ここに言語名を入力
|
|
70
|
+
|
|
71
|
+
python
|
|
72
|
+
|
|
73
|
+
```
|
|
74
|
+
|
|
75
|
+
### 試したこと
|
|
76
|
+
|
|
77
|
+
自分なりにコードを書いたのですが初歩的なところでつまずいているのかもしれずエラーコードを見ても分かりません。
|
|
78
|
+
|
|
79
|
+
とてもレベルの低い質問かもしれませんが、回答してくださればと思います。
|
|
80
|
+
|
|
81
|
+
ここに問題に対して試したことを記載してください。
|
|
82
|
+
|
|
83
|
+
### 補足情報（FW/ツールのバージョンなど）
|
|
84
|
+
|
|
85
|
+
ここにより詳細な情報を記載してください。
|
4
,
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
|
|
1
|
+
####################
|
test
CHANGED
|
File without changes
|
3
、
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -1,103 +1 @@
|
|
|
1
|
-
### 前提・実現したいこと
|
|
2
|
-
|
|
3
|
-
プログラミング超初心者で初めて質問させていただきました。
|
|
4
|
-
|
|
5
|
-
題名にもある通り剰余計算を使わずに2変数x,yの最大公約数を求めるにはどのようにすればよいですか？
|
|
6
|
-
|
|
7
|
-
最大公約数をgcd(x,y)とし、
|
|
8
|
-
|
|
9
|
-
ｘ、ｙがともに偶のとき,gcd(x,y)→2*gcd(x/2,y/2)
|
|
10
|
-
|
|
11
|
-
xが奇,yが偶のとき、gcd(x,y)→gcd(x,y/2)
|
|
12
|
-
|
|
13
|
-
x,yどちらも奇のとき、gcd(x,y)→gcd((x,y)/2,y)
|
|
14
|
-
|
|
15
|
-
という要領で計算します。
|
|
16
|
-
|
|
17
|
-
できれば演算子％を使わずにお願いします。
|
|
18
|
-
|
|
19
|
-
ここに質問の内容を詳しく書いてください。
|
|
20
|
-
|
|
21
|
-
|
|
22
|
-
|
|
23
|
-
|
|
24
|
-
|
|
25
|
-
### 発生している問題・エラーメッセージ
|
|
26
|
-
|
|
27
|
-
|
|
28
|
-
|
|
29
|
-
```
|
|
30
|
-
|
|
31
|
-
def gcd(x, y):
|
|
32
|
-
|
|
33
|
-
if y==0:
|
|
34
|
-
|
|
35
|
-
return x
|
|
36
|
-
|
|
37
|
-
elif x&1==0 and y&1==0 and y!=0:
|
|
38
|
-
|
|
39
|
-
x, y=x//2, y//2
|
|
40
|
-
|
|
41
|
-
return 2*gcd(x, y)
|
|
42
|
-
|
|
43
|
-
elif x&1==0 and y&1==1 and y!=0:
|
|
44
|
-
|
|
45
|
-
x=x//2
|
|
46
|
-
|
|
47
|
-
return gcd(x, y)
|
|
48
|
-
|
|
49
|
-
elif x&1==1 and y&1==0 and y!=0:
|
|
50
|
-
|
|
51
|
-
y=y//2
|
|
52
|
-
|
|
53
|
-
return gcd(x, y)
|
|
54
|
-
|
|
55
|
-
elif x&1==1 and y&1==1 and x<y and y!=0:
|
|
56
|
-
|
|
57
|
-
x, y=x, (y-x)//2
|
|
58
|
-
|
|
59
|
-
return gcd(x, y)
|
|
60
|
-
|
|
61
|
-
else:
|
|
62
|
-
|
|
63
|
-
x, y=(x-y)//2, y
|
|
64
|
-
|
|
65
|
-
return gcd(x, y)
|
|
66
|
-
|
|
67
|
-
|
|
68
|
-
|
|
69
|
-
|
|
1
|
+
#####################################################################
|
|
70
|
-
|
|
71
|
-
に対してエラーが出ます。
|
|
72
|
-
|
|
73
|
-
```
|
|
74
|
-
|
|
75
|
-
|
|
76
|
-
|
|
77
|
-
### 該当のソースコード
|
|
78
|
-
|
|
79
|
-
|
|
80
|
-
|
|
81
|
-
```ここに言語名を入力
|
|
82
|
-
|
|
83
|
-
python
|
|
84
|
-
|
|
85
|
-
```
|
|
86
|
-
|
|
87
|
-
|
|
88
|
-
|
|
89
|
-
### 試したこと
|
|
90
|
-
|
|
91
|
-
自分なりにコードを書いたのですが初歩的なところでつまずいているのかもしれずエラーコードを見ても分かりません。
|
|
92
|
-
|
|
93
|
-
とてもレベルの低い質問かもしれませんが、回答してくださればと思います。
|
|
94
|
-
|
|
95
|
-
ここに問題に対して試したことを記載してください。
|
|
96
|
-
|
|
97
|
-
|
|
98
|
-
|
|
99
|
-
### 補足情報（FW/ツールのバージョンなど）
|
|
100
|
-
|
|
101
|
-
|
|
102
|
-
|
|
103
|
-
ここにより詳細な情報を記載してください。
|
2
/→//
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -36,31 +36,31 @@
|
|
|
36
36
|
|
|
37
37
|
elif x&1==0 and y&1==0 and y!=0:
|
|
38
38
|
|
|
39
|
-
x, y=x/2, y/2
|
|
39
|
+
x, y=x//2, y//2
|
|
40
40
|
|
|
41
41
|
return 2*gcd(x, y)
|
|
42
42
|
|
|
43
43
|
elif x&1==0 and y&1==1 and y!=0:
|
|
44
44
|
|
|
45
|
-
x=x/2
|
|
45
|
+
x=x//2
|
|
46
46
|
|
|
47
47
|
return gcd(x, y)
|
|
48
48
|
|
|
49
49
|
elif x&1==1 and y&1==0 and y!=0:
|
|
50
50
|
|
|
51
|
-
y=y/2
|
|
51
|
+
y=y//2
|
|
52
52
|
|
|
53
53
|
return gcd(x, y)
|
|
54
54
|
|
|
55
55
|
elif x&1==1 and y&1==1 and x<y and y!=0:
|
|
56
56
|
|
|
57
|
-
x, y=x, (y-x)/2
|
|
57
|
+
x, y=x, (y-x)//2
|
|
58
58
|
|
|
59
59
|
return gcd(x, y)
|
|
60
60
|
|
|
61
61
|
else:
|
|
62
62
|
|
|
63
|
-
x, y=(x-y)/2, y
|
|
63
|
+
x, y=(x-y)//2, y
|
|
64
64
|
|
|
65
65
|
return gcd(x, y)
|
|
66
66
|
|
1
ユークリッドの互除法ではありませんでした。
test
CHANGED
|
@@ -1 +1 @@
|
|
|
1
|
-
|
|
1
|
+
剰余演算を使わずに最大公約数を求めるには
|
test
CHANGED
|
@@ -2,7 +2,7 @@
|
|
|
2
2
|
|
|
3
3
|
プログラミング超初心者で初めて質問させていただきました。
|
|
4
4
|
|
|
5
|
-
題名にもある通り
|
|
5
|
+
題名にもある通り剰余計算を使わずに2変数x,yの最大公約数を求めるにはどのようにすればよいですか？
|
|
6
6
|
|
|
7
7
|
最大公約数をgcd(x,y)とし、
|
|
8
8
|
|