[エラーノート]白準#1629乗算(Python):余剰演算の割当て法則

今日の一言
これはアルゴリズムで最適化するのではなく、整数論で最適化します.何も言えない
まず概念を熟知しましょう.

Baekjoon問題リンク

solved.ac>問題>CLASS 4.

質問する

自然数AにBを乗じた数を知りたいです.ただし、購入したい数が非常に大きい場合がありますので、残りの数を求めるためにCに分けるプログラムを作成してください.

入力

1行目A,B,Cはスペースを隔てて順次与えられる.A,B,Cともに2147483647以下の自然数である.

しゅつりょく

出力1行目AにBを乗じた数をCの余剰数で割る.

入力例1

10 11 12

サンプル出力1

4

時間制限:0.5秒(追加時間なし)

メモリ制限:128 MB

の意見を打診

Solution #1

# A ** B % C

import sys

A, B, C = map(int, sys.stdin.readline().rstrip().split())
print(A ** B % C)

ははははははははははははは
もちろんタイムアウトです.

Solution #2

この問題のアルゴリズム分類は分割征服を用いた反復二乗である.
分割征服によるA**Bの結果は以下の通りである.

def fpow(A, B):
	if B == 1:
		return A
	x = fpow(A, B//2)
    return x*x if B%2 == 0 else x*x*A

正直、タイムアウトの原因は残りの演算ではなく、二乗演算だと思います.

import sys

A, B, C = map(int, sys.stdin.readline().rstrip().split())

def fpow(A, B):
    if B == 1:
        return A
    x = fpow(A, B//2)
    return x**2 if B%2 == 0 else x**2 * A

print(fpow(A, B) % C)

コミットされますが、この解答もタイムアウトします.

Solution #3

崩壊に陥り
このリンクの解答を見て残りの分配法則を学びました.
(A*B) % C = (A%C) * (B%C) % C
AとBを掛け合わせた場合、数が大きくなったら残りの数を掛け合わせて、早めに減らしても大丈夫!
残りの演算を事前に完了しなければA**Bが完了し、分割征服によって得られたとしても.
もしBが本当に大きいなら(この問題では、A、B、Cはいずれも2147483647以下の自然数です).
重要なのは、その値を持つだけで時間がかかることを理解することです.

に答える

# A ** B % C

import sys

A, B, C = map(int, sys.stdin.readline().rstrip().split())

def f(A, B, C):
    if B == 1:
        return A % C
    x = f(A, B//2, C)
    return x**2 % C if B%2 == 0 else (x**2 % C) * (A%C) % C

print(f(A, B, C))

指数が奇数の場合,上記の残分配法則を用いて重畳計算を行った.