Pythonで理解する蟻本「2-7 Minimum Scalar Product（2008 Round1A A）」(p.117)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-7 Minimum Scalar Product（2008 Round1A A）」(p.117)
のコードをPythonで書き直したものとなっています。

入力

入力例1

3
1 3 -5
-2 4 1

入力例2

5
1 2 3 4 5
1 0 1 0 1

解答

# 入力
n = int(input())
v1 = list(map(int,input().split()))
v2 = list(map(int,input().split()))

v1.sort()
v2.sort()
ans = 0
for i in range(n):
    ans += v1[i] * v2[n - i - 1]
print(ans)

kuruton456 2021-01-07 08:00 読者になる

広告を非表示にする

• もっと読む

コメントを書く

Pythonで理解する蟻本「2-6 Carmichael Numbers（UVa No.10006）」(p.114)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 Carmichael Numbers（UVa No.10006）」(p.114)
のコードをPythonで書き直したものとなっています。

入力

入力例1

17

入力例2

561

入力例3

4

2のべき乗の和として表す方法

def mod_pow(x, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * x % mod    # 最下位ビットが立っているときにx^(2^i)を掛ける
        x = x * x % mod        # xを順次二乗していく
        n >>= 1
    return res

再帰関数を使う方法

def mod_pow(x, n, mod):
    if n == 0:
        return 1
    res = mod_pow(x * x % mod, n // 2, mod)
    if n & 1:
        res = res * x % mod
    return res

組み込み関数powを使う方法（重要！）

実は、pythonにはO(log n)でべき乗の計算を行うことができる、pow関数が存在します。

この関数は組み込み関数であるため、インポートせずに使うことができます。

競技プログラミングでべき乗を計算する際には、迷わずこのpow関数を使いましょう。

pow(x, n, mod)

解答

import sys

# 入力
n = int(input())

# 素数判定O(√n)
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n != 1    # 1の場合は例外

if is_prime(n):
    print('No')
    sys.exit()    # nが素数であれば、'No'を出力してプログラムを終了する

for x in range(2, n):
    if pow(x, n, n) != x:
        print('No')
        sys.exit()    # x^n≡x(mod n) が成り立たないようなxが存在すれば、'No'を出力してプログラムを終了する

print('Yes')

kuruton456 2021-01-04 08:00 読者になる

広告を非表示にする

• もっと読む

コメントを書く

Pythonで理解する蟻本「2-6 区間内の素数の個数」(p.113)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 区間内の素数の個数」(p.113)
のコードをPythonで書き直したものとなっています。

入力

入力例

22801763489 22801787297

解答

MAX_L = 10 ** 6
MAX_SQRT_B = 10 ** 6

is_prime = [True] * MAX_L
is_prime_small = [True] * MAX_SQRT_B

# [a,b)の整数に対して篩を行う。is_prime[i - a] = True ⇔ iが素数
def segment_sieve(a, b):
    i = 0
    while i * i < b:
        is_prime_small[i] = True
        i += 1
    i = 0
    for i in range(b - a):
        is_prime[i] = True
    
    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False    # [2,√b)の篩
                j += i
            j = (a + i - 1) // i * i
            while j < b:
                is_prime[j - a] = False    # [a,b)の篩
                j += i
        i += 1

a, b = map(int,input().split())
segment_sieve(a, b)
ans = sum(is_prime[:b - a])
print(ans)

kuruton456 2021-01-01 08:00 読者になる

広告を非表示にする

• もっと読む

コメントを書く

Pythonで理解する蟻本「2-6 素数の個数」(p.111)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 素数の個数」(p.111)
のコードをPythonで書き直したものとなっています。

入力

入力例1

11

入力例2

1000000

解答

MAX_N = 10 ** 6

prime = [None] * MAX_N    # i番目の素数
is_prime = [True] * (MAX_N + 1)    # is_prime[i]がTrueならiは素数

# n以下の素数の数を返す
def sieve(n):
    p = 0
    for i in range(n + 1):
        is_prime[i] = True
    is_prime[0] = is_prime[1] = False
    for i in range(2, n + 1):
        if is_prime[i]:
            prime[p] = i
            p += 1
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return p

n = int(input())
ans = sieve(n)
print(ans)

kuruton456 2020-12-29 08:00 読者になる

広告を非表示にする

• もっと読む

コメントを書く

Pythonで理解する蟻本「2-6 素数判定」(p.110)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 素数判定」(p.110)
のコードをPythonで書き直したものとなっています。

入力

入力例

295927

素数判定（O(√n)）

# 素数判定O(√n)
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n != 1    # 1の場合は例外

実行結果

False

約数の列挙（O(√n)）

# 約数の列挙O(√n)
def divisor(n):
    res = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
        i += 1
    return res

実行結果

[1, 295927, 541, 547]

素因数分解（O(√n)）

# 素因数分解O(√n)
def prime_factor(n):
    res = {}
    i = 2
    while i * i <= n:
        while n % i == 0:
            if not i in res:
                res[i] = 0
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res

実行結果

{541: 1, 547: 1}

kuruton456 2020-12-26 08:00 読者になる

広告を非表示にする

• もっと読む

コメントを書く

Pythonで理解する蟻本「2-6 双六」(p.108)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 双六」(p.108)
のコードをPythonで書き直したものとなっています。

入力

入力例

4 11

拡張ユークリッドの互除法

def extgcd(a, b):
    d = a
    if b != 0:
        d, y, x = extgcd(b, a % b)
        y -= (a // b) * x
    else:
        x = 1
        y = 0
    return d, x, y

解答

# 入力
a, b = map(int,input().split())

# 拡張ユークリッドの互除法
def extgcd(a, b):
    d = a
    if b != 0:
        d, y, x = extgcd(b, a % b)
        y -= (a // b) * x
    else:
        x = 1
        y = 0
    return d, x, y

d, x, y = extgcd(a, b)

if d == 1:
    L = [0] * 4
    if x > 0:
        L[0] += x
    else:
        L[2] += -x
    if y > 0:
        L[1] += y
    else:
        L[3] += -y
    print(*L)
else:
    print(-1)

kuruton456 2020-12-23 00:00 読者になる

広告を非表示にする

• もっと読む

コメントを書く

Pythonで理解する蟻本「2-6 線分上の格子点の個数」(p.107)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 線分上の格子点の個数」(p.107)
のコードをPythonで書き直したものとなっています。

入力

入力例

1 11
5 3

最大公約数を求める関数

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

解答

# 入力
x1, y1 = map(int,input().split())
x2, y2 = map(int,input().split())

# 最大公約数を求める関数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

ans = gcd(abs(x1 - x2), abs(y1 - y2)) - 1
print(ans)

kuruton456 2020-12-20 08:00 読者になる

広告を非表示にする

• もっと読む

コメントを書く