競技プログラミングで解けなかった箇所を端的にまとめ、補足説明を足しました。
べき乗関数
pow(3, 2)
- 3の2乗（3^2）を計算します。
- 結果:
9
print(pow(3, 2)) # 出力: 9
pow(3, 2, 5)
-3の2乗（3^2）を5で割ったあまりを計算します。
- 素早く計算できる仕組みになっており、大きな数のべき乗でも効率的に余りを求めることができます。
print(pow(3, 2, 5)) # 出力: 4
通常の余りを求める作業との比較
- 2**1000000000 % 3 と pow(2, 1000000000, 3) を比較してみます。
result1 = 2**1000000000 % 3
result2 = pow(2, 1000000000, 3)
print(result1) # 出力: 1
print(result2) # 出力: 1
- 2**1000000000 % 3 は非常に大きな数の計算となり、時間がかかる可能性があります。
- pow(2, 1000000000, 3) は効率的に計算でき、短時間で結果を得られます。
何桁かを知る
len(str(N))
- 整数Nの桁数を取得します。
- int 型の整数Nを str 型に変換し、その長さを len 関数で取得します。
コードをコピーする
N = 12345
num_digits = len(str(N))
print(num_digits) # 出力: 5
分数の形を○○で割ったときのあまり
フェルマーの小定理
- フェルマーの小定理を利用して、分数の形を○○で割ったときのあまりを求めることができます。
- フェルマーの小定理: a^(p-1) ≡ 1 (mod p) ただし、p は素数で a は p と互いに素な整数。
具体例
- a / b を p で割ったあまりを求めたいとき、 a * b^(p-2) % p として計算します。
a = 10
b = 3
p = 7
# b^(p-2) % p を計算
b_inv = pow(b, p-2, p)
# a * b_inv % p を計算
result = (a * b_inv) % p
print(result) # 出力: 5
listの中のある文字列の出現回数
list.count()
- リスト内の特定の要素の出現回数を数えます。
my_list = ['apple', 'banana', 'apple', 'cherry', 'apple']
count_apple = my_list.count('apple')
print(count_apple) # 出力: 3
以上、競技プログラミングで使えなかった関数とその補足説明をまとめました。