# プログラミング体験会2022 おまけ
時間が余った方 or 元から理解している方に向けた問題となります。
自信のある方はチャレンジしてみましょう！
解説でわからないところがあったらDiscordで質問してみましょう。
## Hello, World! 追加問題
`traP21welcome` と出力してみましょう
### 答え
:::spoiler
```"Hello, World"``` を```"traP21welcome"```に変更して実行すればよいです。
```python=
print("traP21welcome")
```
:::
## 四則演算 追加問題
半径$46418\rm{m}$の円の面積を出力してみましょう。
円周率は$3.14$とします。
### 答え
:::spoiler
下記の通りに記述すればよいです。
```python=
print(46418 * 46418 * 3.14)
```
:::
## 型・変数 追加問題
```東京``` , ```東北``` , ```日本``` と ```工業大学``` をそれぞれ組み合わせた文を変数を用いて出力してみましょう。
```
東京工業大学
東北工業大学
日本工業大学
```
### 答え
:::spoiler
各変数に文字を格納して、``+``で合体して出力しましょう。
```python=
tk = "東京"
th = "東北"
jp = "日本"
uv = "工業大学"
print(tk + uv)
print(th + uv)
print(jp + uv)
```
:::
## 真理値・if文 追加問題
住んでいる場所が`東京`なら`都会人` `大阪`なら`大阪人` それ以外なら`田舎者` と出力してください
プログラムの始めは↓をコピペしてください
```python=
# s に住んでいる都道府県を入れよう
s = "神奈川"
```
### 答え
:::spoiler
比較は文字列にも使えます。
```python=
s = "神奈川"
if s == "東京":
print("都会人")
elif s == "大阪":
print("大阪人")
else:
print("田舎者")
```
:::
## while文 追加問題
$100!$ の値を求めてください
### 答え
:::spoiler
$n$ を減らしながら $\rm{ans}$ に掛けていきましょう。
```python=
ans = 1
n = 100
while n > 0:
ans *= n
n -= 1
print(ans)
```
解
```
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
```
でっかい解...w
:::
## おまけ1
次の積分の値を小数第二位まで求めてください。
$$
\int_1^3 x^{x}dx
$$
### 解答
:::spoiler
```
13.72
```
:::
### 解説
:::spoiler
不定積分はできない (はず) なので、プログラムを使って近似解を求めましょう。
いい感じに分割して区分求積法みたいな感じで計算すれば近い数が出せそうです。
誤差が心配な場合は、挟んで評価することができるので (単調増加より)、そうすると安心できます。
実装例
```python=
start = 1
end = 3
n = 100000
x = start
dx = (end - start) / n
ans_min = 0
ans_max = 0
while x < end:
ans_min = ans_min + (x ** x) * dx
x = x + dx
ans_max = ans_max + (x ** x) * dx
print(ans_min)
print(ans_max)
```
:::
## おまけ2
フィボナッチ数列とは、以下の性質を満たすような数列です。
$$
a_0 = 0\\
a_1 = 1\\
a_{n+2} = a_{n+1} + a_n\ (n \geq 0)
$$
$a_{2021}$ が
```
103403667628715722063009909327061300875981200753730889520990624292849108119214493482063528806819576007158742175419927124502481168965722136154755586890829043992389175621134497217727779590297650250983717856207414605867319204991465267104018708957680627600342671365497667589884434029642671606713477509224034499712666720145411344729881083833640314311689691698537756174773310415882716916332463907829625789653143023739931304314821
```
であることを確かめてください。
### 解説
:::spoiler
このような大きな数はデフォルトでは扱えないような言語も多いのですが、Pythonの整数は多倍長整数 (上限がない) ので、このような数も簡単に扱うことができます。
実装例
```python=
ans = 103403667628715722063009909327061300875981200753730889520990624292849108119214493482063528806819576007158742175419927124502481168965722136154755586890829043992389175621134497217727779590297650250983717856207414605867319204991465267104018708957680627600342671365497667589884434029642671606713477509224034499712666720145411344729881083833640314311689691698537756174773310415882716916332463907829625789653143023739931304314821
n = 2
a = 1
a_before = 0
while n <= 2021:
tmp = a_before
a_before = a
a = a + tmp
n += 1
print(a == ans)
```
:::
## おまけ3
完全数とは、自分自身を除いた正の約数の和に等しくなる自然数のことです。
(例 : $6 = 1 + 2 + 3$)
現在見つかっている完全数はすべて偶数で、奇数の完全数が存在するかどうかは未解決らしいです。
完全数を小さい順にいくつか求めてみましょう。ただし、求める完全数はすべて偶数であると仮定してよいです。
レベル1: 3つ
レベル2: 4つ
レベル3: 5つ
:::spoiler レベル3 のヒント
完全数の性質について調べてみましょう。
:::
<br>
### 解答
:::spoiler 3つ
```
6
28
496
```
:::
:::spoiler 4つ
```
6
28
496
8128
```
:::
:::spoiler 5つ
```
6
28
496
8128
33550336
```
:::
### 解説
:::spoiler 3つ
順番に調べていくようなコードを書くことで、3つまでは求めることができます。
実装例
```python=
n = 2
count = 0
while count < 3:
i = 1
div_sum = 0
while i < n:
if n % i == 0:
div_sum = div_sum + i
i = i + 1
if div_sum == n:
print(n)
count = count + 1
n = n + 2
```
:::
:::spoiler 4つ
上のコードで4つ目も求めてみようとすると、paiza.io ではTimeoutとなってしまいます。
(手元環境で実行すると5秒ぐらい待てば終わります)
そこで、改善案を考えます。
$n$ の約数である $i$ を見つけたとき、$j = \frac{n}{i}$ とすることで、$i \neq j$ であればもう1つ約数を見つけることができます。
証明は省きますが、このことから $i ^2 \leq n$ となるような $i$ についてのみ調べ、それぞれについて $\frac{n}{i}$ も考えることで、すべての約数を網羅できることがわかります。
この方法で求めた約数和には自分自身も含まれていることも注意しましょう。
実装例
```python=
n = 2
count = 0
while count < 4:
i = 1
div_sum = 0
while i * i <= n:
if n % i == 0:
div_sum = div_sum + i
if i * i != n:
div_sum = div_sum + n // i
i = i + 1
if div_sum == n * 2:
print(n)
count = count + 1
n = n + 2
```
:::
:::spoiler 5つ
↑では5つ目は求めることができません。
(手元で20分ぐらい動かしても終わりませんでした)
完全数の性質について調べてみると、どうやら偶数の完全数は $2^{p-1}(2^p-1)$ ($p$ は素数) の形に限るそうです。
素数かどうかの判定は面倒なので、とりあえず $p$ を自然数として試してみると、それでも十分間に合うことが分かります。
実装例
```python=
p = 1
count = 0
while count < 5:
i = 1
n = 2 ** (p - 1) * (2 ** p - 1)
div_sum = 0
while i * i <= n:
if n % i == 0:
div_sum = div_sum + i
if i * i != n:
div_sum = div_sum + n // i
i = i + 1
if div_sum == n * 2:
print(n)
count = count + 1
p = p + 1
```
7つ目まで同様の方法で求めることができます。
:::
## おまけ4
$$
9007199254740997x + 92709568269121y = 1
$$
を満たすような整数 $x,y$ を求めてください。
ただし、$9007199254740997$ と $92709568269121$ は互いに素です。
:::info
このような問題を解くのには再帰関数という方法を一般的には用いるのですが、今回扱った方法だけでも (難しいですが) 解くことができます。
再帰関数を知っている方も、頭の体操だと思って再帰関数を使わない方法に挑戦してみましょう。
:::
:::spoiler ヒント
ユークリッドの互除法を用いた不定方程式の解き方では、一度上から下まで書いた後に下から順に見ていきます。
これを今回扱った方法だけで表現するのは難しいです。
どうにか上から見ていくような解き方にできれば、今回扱った方法でも計算できそうです。
:::
<br>
### 解答
:::spoiler
```
19849496936897 -1928478121028548
```
(解答は一意ではないので、方程式を満たしていればOKです)
:::
### 解説
:::spoiler
ユークリッドの互除法を使った解法をプログラムとして実装します。かなり難しいと思います。問題作成者は紙とペンを使って数十分考えました。
以下、軽い解説です。
$ax + by = 1$ を解く場合を考えます。($a$ と $b$ は互いに素とします)
$k_1=a, k_2=b$ として、
$$
k_1 = p_1k_2 + k_3\\
k_2 = p_2k_3 + k_4\\
\dots
$$
というふうにユークリッドの互除法が行われていくとします。
ここで、$k_{n+2} = -p_nk_{n+1} + k_{n}$ より、$k_{n+1}$ と $k_n$ をそれぞれ $ax+by$ の形で表すことができれば、$k_{n+2}$ についても同様の形に表すことができます。
また、$a$ と $b$ が互いに素ならば $k_n=1$ となるような $n$ は必ず存在します。(証明略)
つまり、$ax_n + by_n = k_n$ を満たす $(x_n,y_n)$ と $ax_{n+1} + by_{n+1} = k_{n+1}$ を満たす $(x_{n+1},y_{n+1})$ を常に持っておくようにしながら $n$ を大きくしていくことで、最終的に $ax + by = 1$ を満たす $x,y$ を求めることができます。
初期条件は一見すると難しいですが、$k_1, k_2$ をそれぞれ $ax+by$ の形で表すような $x,y$ を考えれば良いので、$k$ の定義からそれぞれ $(1,0)$, $(0,1)$ です。
実装例
```python
a = 9007199254740997
b = 92709568269121
x_before = 1
y_before = 0
x = 0
y = 1
while a % b != 0:
p = a // b
q = a % b
x_tmp = x_before - p * x
y_tmp = y_before - p * y
x_before = x
y_before = y
x = x_tmp
y = y_tmp
a = b
b = q
print(x, y)
print(9007199254740997 * x + 92709568269121 * y == 1)
```
参考までに、再帰関数を使った方法も紹介します。今回の体験会では扱っていない方法を使っています。
詳しい説明はここではしませんが、これは数学と同じような順番 (一度上から下まで書いていって、下から順番に見ていく) で計算を行っています。
もっと知りたい方は「再帰関数」「拡張ユークリッドの互除法」で調べてみましょう。
```python
def extgcd(a, b):
if b == 0:
return 1, 0
y, x = extgcd(b, a % b)
y = y - a // b * x
return x, y
a = 9007199254740997
b = 92709568269121
x, y = extgcd(a, b)
print(x, y)
print(9007199254740997 * x + 92709568269121 * y == 1)
```
:::
## おまけ5(04/24 追加)
$30$ から $60$ までの数で 素数の場合は Prime それ以外の場合は その数字を出力してください。
### 出力例
$10$ から $29$ の場合
:::spoiler
```
10
Prime
12
Prime
14
15
16
Prime
18
Prime
20
21
22
Prime
24
25
26
27
28
Prime
```
:::
### 解答
:::spoiler
```
30
Prime
32
33
34
35
36
Prime
38
39
40
Prime
42
Prime
44
45
46
Prime
48
49
50
51
52
Prime
54
55
56
57
58
Prime
60
```
:::
### 解答コード例
:::spoiler
```python=
i = 30
while i <= 60:
j = 2
isPrime = False
while j < i:
if i % j == 0:
break
j += 1
if j == i:
isPrime = True
if isPrime:
print("Prime")
else:
print(i)
i += 1
```
:::
### 解説
:::spoiler
$2$ より大きいある数が素数であるかどうかは $2$ から その数$-1$ までで割り切ることができるかどうかで判定できます。
割り切れる $=$ 余りが$0$ なので、```%```を用いて余りを求めればよいです。
:::
## おまけ6 (4/24 追加)
次の三次方程式は自然数解を1つ持ちます。それを求めてください。
```
x^3 + 3218677114060974854681101264677364361962573 x^2 + 1840445506533666033986484884603728067424458945838727730719646373755070770555336789280 x - 2272154925661249289543362932502122952106062554786355558781247264528866708742672195963818341500 = 0
```
### 解答
:::spoiler
```
1234567890
```
:::
### 解説
:::spoiler
係数の大きさからなんとなく察した方もいるかもしれませんが、体験会の演習のように総当たりで求めようとするには計算時間が足りません。
ここで、`問題文の左辺` $=f(x)$ とすると、$x>0$ で $f(x)$ は単調増加なことがわかります (微分したときどうなるか考えてみるとわかります)。
さて、競技プログラミングなどでよく使われるテクニックに二分探索というものがあります。
二分探索は
- 任意の $k$ について、求める解が $k$ より大きいか小さいか
を判定することができる場合に使うことができます。
今回の場合、単調増加がわかっているので、求める解を $x_1$ とすると $f(k) > 0 \Rightarrow k > x_1$ 、 $f(k)<0 \Rightarrow k<x_1$ と判定することができます。
二分探索ではまず、解の存在する範囲を定め、その中間点について調べます。
そして、もしその中間点より解が大きいなら上半分、小さいなら下半分の範囲について同様の操作を繰り返します。
この操作では指数的に範囲が小さくなっていくため、だいたい $\log_2 N$ 回で計算することができます($N$ は最初に定めた範囲の大きさとする)。
以下では、$f(right) \geq 0, f(left) < 0$ を満たすようにしながら `right`、`left` を互いに近づけています。そして、`right - left == 1` となったとき、(自然数解の存在が保証されているため) `right` が解となります。
```python
left = 0
right = 100000000000000000000000000000000000000000000000000000000000000
while left + 1 < right:
mid = (left + right) // 2
if mid ** 3 + 3218677114060974854681101264677364361962573 * (mid ** 2) + 1840445506533666033986484884603728067424458945838727730719646373755070770555336789280 * mid - 2272154925661249289543362932502122952106062554786355558781247264528866708742672195963818341500 >= 0:
right = mid
else:
left = mid
print(right)
```
:::