Python による左バイナリ法の実装

バイナリ法はべき乗を高速に計算するアルゴリズムである．

バイナリ法で を計算する際， を二進展開した結果を右から見る方法 (右バイナリ法) と左から見る方法 (左バイナリ法) がある． 以下では，Python による左バイナリ法の実装を紹介する．

def binary(a, k):
    """
    左バイナリ法
    :return: a ** k
    """
    check = 1 << max(0, k.bit_length() - 1)
    x = 1
    while check:
        x *= x
        if k & check:
            x *= a
        check >>= 1
    return x


def binary_mod(a, k, n):
    """
    左バイナリ法
    :return: a ** k % n
    """
    check = 1 << max(0, k.bit_length() - 1)
    x = 1
    while check:
        x = x * x % n
        if k & check:
            x = x * a % n
        check >>= 1
    return x


def ex_binary_mod(k1, k2, a1, a2, n):
    """
    拡張左バイナリ法
    :return: a1 ** k1 * a2 ** k2
    """
    check = 1 << max(0, max(k1, k2).bit_length() - 1)
    x = 1
    while check:
        x = x * x % n
        if k1 & check:
            x = x * a1 % n
        if k2 & check:
            x = x * a2 % n
        check >>= 1
    return x

AOJ0022

Maximum Sum Sequence | Aizu Online Judge

while True:
    n = int(input())
    if n == 0:
        break
    s = [int(input())]
    for i in range(1, n):
        a = int(input())
        s.append(max(a, a + s[i - 1]))
    print(max(s))

AOJ0021

Parallelism | Aizu Online Judge

n = int(input())
for i in range(n):
    x1, y1, x2, y2, x3, y3, x4, y4 = map(float, input().split())
    c1 = (y1 - y2) * (x3 - x4)
    c2 = (y3 - y4) * (x1 - x2)
    if abs(c1 - c2) < 1e-10:
        print('YES')
    else:
        print('NO')

AOJ0020

Capitalize | Aizu Online Judge

s = input()
print(s.upper())

AOJ0019

Factorial | Aizu Online Judge

from math import factorial

n = int(input())
print(factorial(n))

AOJ0018

Sorting Five Numbers | Aizu Online Judge

s = sorted(list(map(int, input().split())), reverse=True)
print(s[0], s[1], s[2], s[3], s[4])

AOJ0017

Caesar Cipher | Aizu Online Judge

#include <iostream>

using namespace std;

int main() {
    string s;
    while (getline(cin, s)) {
        while (true) {
            for (int i = 0; i < s.length(); ++i) {
                if (s[i] == ' ' || s[i] == '.') {
                    continue;
                }
                if (s[i] == 'z') {
                    s[i] -= 26;
                }
                ++s[i];
            }

            if (s.find("the") != string::npos || s.find("this") != string::npos || s.find("that") != string::npos) {
                cout << s << endl;
                break;
            }
        }

    }

    return 0;
}