几种数论基础函数的实现

本页主要包含以下几种基础函数的实现：

• 快速幂
• 埃氏筛

Reference：

• 快速幂算法 超详细教程

P1226【模板】快速幂

题目描述

给你三个整数 $a,b,p$，求 $a^b \bmod p$。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

输入输出样例 #1

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示

样例解释

$2^{10} = 1024$，$1024 \bmod 9 = 7$。

数据规模与约定

对于 $100\%$ 的数据，保证 $0\le a,b < 2^{31}$，$a+b>0$，$2 \leq p \lt 2^{31}$。

解决方案

我们采用Reference中的第二种方法，这种方法更好理解一些。

def quick_power(base, power):
    result = 1
    while power > 0:
        if power % 2 != 0:
            power -= 1
            # 随时取模可以进一步降低时间复杂度
            result *= base % p
        power /= 2
        base *= base % p

    return result
        

if __name__ == "__main__":
    a, b, p = map(int, input().split())

    ans = quick_power(a, b)
    print("{}^{} mod {}={}".format(a, b, p, ans%p))

Bingo!

P1218 [USACO1.5] 特殊的质数肋骨 Superprime Rib

题目描述

农民约翰的母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。

农民约翰确定他卖给买方的是真正的质数肋骨，是因为从右边开始切下肋骨，每次还剩下的肋骨上的数字都组成一个质数。

举例来说：$7\ 3\ 3\ 1$ 全部肋骨上的数字 $7331$ 是质数；三根肋骨 $733$ 是质数；二根肋骨 $73$ 是质数；当然,最后一根肋骨 $7$ 也是质数。$7331$ 被叫做长度 $4$ 的特殊质数。

写一个程序对给定的肋骨的数目 $n$，求出所有的特殊质数。$1$ 不是质数。

输入格式

一行一个正整数 $n$。

输出格式

按顺序输出长度为 $n$ 的特殊质数,每行一个。

输入输出样例 #1

输入 #1

4

输出 #1

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

说明/提示

【数据范围】
对于 $100\%$ 的数据，$1\le n \le 8$。

题目翻译来自NOCOW。

USACO Training Section 1.5

解决方案

这道题最让我吃惊的地方是居然用到了DFS，不妨先来看看我的第一版代码：

import sys

if __name__ == "__main__":
    n = int(input())       
        
    num = 10 ** (n-1)
    edge = 10 ** n - 1

    arr = [True for _ in range(edge+1)]
    primes = []

    for i in range(num, edge+1):
        flag = True
        j = i
        ii = []
        while i:
            ii.append(i)
            i //= 10

        for i in ii:
            if i not in primes:
                flag = False
                break

        if flag:
            print(j)

这一版代码虽然在筛选质数的过程中用到了埃氏筛，高效降低了时间复杂度，但是由于随后在寻找答案的过程中进行了及其低效的逐个枚举，仍然使整段代码的时间复杂度达到了一个不可接受的程度。

随后在查看题解的过程中我才恍然大悟，找答案的过程不也是一个搜索吗，从一个数的第一位开始搜索，如果这一位是质数就接着判断下一位，这样一来就大大降低了时间复杂度：

import sys

def dfs(num, length):
    if length == n:
        print(num)
    for i in range(1, 10):
        if (num*10 + i) in primes:
            dfs(num*10+i, length+1)

if __name__ == "__main__":
    n = int(input())
               
    num = 10 ** (n-1)
    edge = 10 ** n - 1

    arr = [True for _ in range(edge+1)]
    primes = []

    for i in range(2, edge+1):
        if arr[i]:
            primes.append(i)
            for j in range(i+i, edge+1, i):
                arr[j] = False

    dfs(0, 0)

Bingo!