首页 > 其他分享 >蓝桥杯真题(数论)

蓝桥杯真题(数论)

时间:2023-02-01 23:25:45浏览次数:56  
标签:arr return gcd 真题 数论 质数 蓝桥 int x2

数论

倍数问题

倍数问题一般都会想到取模。这里要找三个数的和是K的倍数,直接暴力肯定超时。注意到K的范围,最大取到1e3,可以用O(n^2)的算法。

要使得相加为K的倍数,只需要余数相加为K的倍数,所以可以预处理一下所有数模K的余数,因为题目问的是最大的和,所以要计算出K以内的余数对应的最大值,即mods[i]=max(v for v in arr if v%K==i)

注意可能有多个数的余数相同,所以还要计算一下次大数和次次大数。

import sys; readline = sys.stdin.readline
read = lambda: [int(x) for x in readline().split()]
alloc = lambda *s: len(s) != 1 and [alloc(*s[1:]) for i in range(int(s[0]) + 2)] or [0] * int(s[0] + 2)

N, K = read()
arr = read()

mods1 = [-1] * (K + 1) # 最大数
mods2 = [-1] * (K + 1) # 次大数
mods3 = [-1] * (K + 1) # 次次大数

for v in arr:
    x = v % K
    if v >= mods1[x]:
        mods3[x] = mods2[x]
        mods2[x] = mods1[x]
        mods1[x] = v
    elif v >= mods2[x]:
        mods3[x] = mods2[x]
        mods2[x] = v
    elif v >= mods3[x]:
        mods3[x] = v

ans = 0

for i in range(K):
    for j in range(K):
        k = (K - i - j) % K
        a = mods1[i]
        b = mods2[j] if i == j else mods1[j]
        if k == i and k == j:
            c = mods3[k]
        elif k == i or k == j:
            c = mods2[k]
        else:
            c = mods1[k]
        if a == -1 or b == -1 or c == -1: continue
        if a + b + c > ans: ans = a + b + c
print(ans)

寻找整数

一眼看出是中国剩余定理,不过需要选出质数作为模数。

证明不用考虑非质数:

若x % a == b

对于非质数a,存在一个质数k,使得a == kt

x == am + b == k(tm) + b

x % k == b % k == b'

非质数的等式可以替换为质数的等式,故只需考虑质数

中国剩余定理:

$m_1, m_2, \dots, m_n$ 两两互质
$$
x \equiv a_1 (\mod m_1) \
x \equiv a_2 (\mod m_2) \
\vdots \
x \equiv a_n (\mod m_n) \
$$
x has a unique solution modulo m ($m = m_1m_2\dots m_n$)
$$
M_k = m / m_k \
M_ky_k \equiv 1(\mod m_k) \
x \equiv a_1M_1y_1 + a_2M_2y_2 + \dots + a_nM_ny_n(\mod m)
$$

这里yk是Mk关于mk的逆元

求逆元:

Mk*yk % mk == 1推出Mk*yk + mk*k == 1

套用扩展欧几里得算法:yk, _ = exgcd(Mk, mk)

扩展欧几里得算法:

// 求x, y,使得ax + by = gcd(a, b)
def exgcd(a, b):
if b == 0: return 1, 0
y, x = exgcd(b, a % b)
return x, y - a // b * x

证明:

(a,b) == (b,a % b)

存在x和y使得ax + by == gcd(a, b) == d

存在n和m使得bn + (a%b)m == d

有bn + (a - a/b * b)m == am + b(n - a/b * m) == d

因此:

x == m

y == n - a/b * m

exgcd(b, a % b)这一递归调用即求出n和m,分别赋值给y和x

ps = {
    2:1,
    3:2,
    5:4,
    7:4,
    11:0,
    13:10,
    17:0,
    19:18,
    23:15,
    29:16,
    31:27,
    37:22,
    41:1,
    43:11,
    47:5
    }
# ax + by == gcd(a, b)
def exgcd(a, b):
    if b == 0: return 1, 0
    y, x = exgcd(b, a % b)
    return x, y - a // b * x

M = 1
ans = 0
for k in ps: M *= k
for m, r in ps.items():
    Mi = M // m
    t, _ = exgcd(Mi, m) # t是Mi关于m的逆元
    ans += r * Mi * t

print(ans % M)

质数判定

注意N最大可以取到1e16,所以不能使用筛质数的方法。

因为T最大取到1e5,因此如果对每个质数使用普通的质数判定方法(O(根号n))会超时。

这里需要使用Miller Rabin算法判定质数(O(log^3(n)))

二次探测定理:

对于质数p,若x^2 = 1(mod p),则小于p的解只有x1 = 1,x2 = p - 1

证明:

x ^ 2 - 1 = 0 (mod p),=> (x - 1)(x + 1) = 0(mod p) => x = 1 或 x = p - 1

对于一个要判定的数p,把p - 1分解为u*2^t。我们随机选一个数a,计算a^u,将该数不断自乘,如果自乘后模p为1,根据二次探测定理,自乘前要么为1要么为p-1,自乘t次后,我们得到a^(p-1),根据费马小定理,该数模p为1。

若p通过一次测试,则p不是素数的概率为25%

那么经过t轮测试,p不是素数的概率为(0.25)^t。这里进行10轮测试,几乎不会出错。

import sys
import random

def qpow(a, n, m):
    res = 1
    while n:
        if n & 1: res = res * a % m
        a = a * a % m
        n >>= 1
    return res % m

def MR(p):
    if p == 1: return False
    u = p - 1; t = 0
    while u % 2 == 0:
        u >>= 1
        t += 1
    for _ in range(10):
        a = random.randint(0, 1 << 32) % (p - 1) + 1
        v = qpow(a, u, p)
        for _ in range(t):
            o = v; v = v * v % p
            if v == 1 and o != 1 and o != p - 1: return False
        if v != 1: return False
    return True

readline = sys.stdin.readline
T = int(readline())

for _ in range(T):
  x = int(readline())
  print(1 if MR(x) else 0)

最大比例

从等比数列中选出若干数,要求出可能的最大公比。根据题意,给定的数中可能有重复,需要去重。

等比数列中的数可以表示为a0*r**k[i]

可以让所有数除以最小的一项,从而消掉a0。这里的除不是直接除,而是得到最简分数:ai / bi

做完这一步后,所有数可以表示为r**x[i],这里的r不能再表示为某个数的幂。

要找到一个最大的公比,也就是要找到能够整除所有r**x[i]的最大的数。

r可以是一个分数,可以表示为p/qai / bi = r**x[i] = (p ** xi)/(q ** xi)

因此答案就是p**gcd(x1,x2,...) / q**gcd(x1,x2,...)

这里要用辗转相减法进行如下推导:

f(p**x1, p**x2) = p**gcd(x1,x2) = a**gcd(x2, x1-x2) = f(p**x2, p**(x1-x2))

即:f(a1, a2) = f(a2, a1 // a2)

import sys; readline = sys.stdin.readline
read = lambda: [int(x) for x in readline().split()]
alloc = lambda *s: len(s) != 1 and [alloc(*s[1:]) for i in range(int(s[0]) + 2)] or [0] * int(s[0] + 2)
import math

read()
arr = read()
arr = sorted(list(set(arr)))
n = len(arr)

nu = []
de = []

for x in arr[1:]:
    gcd = math.gcd(x, arr[0])
    a = x // gcd
    b = arr[0] // gcd
    nu.append(a)
    de.append(b)

def gcd_sub(a, b):
    if a < b: return gcd_sub(b, a)
    if b == 1: return a
    return gcd_sub(b, a // b)

up = nu[0]; down = de[0]
for a, b in zip(nu[1:], de[1:]):
    up = gcd_sub(up, a)
    down = gcd_sub(down, b)

print('%d/%d' % (up, down))

序列求和

所有数都可以表示为p1 ^ n1 * p2 ^ n2 * ...pi为质数。

因此一个数的约数个数即为(n1 + 1) * (n2 + 1) * ...

S[i] == x ,则有x == p1 ^ n1 * p2 ^ n2 * ..(n1 + 1) * (n2 + 1) * ... == i

因为i最大取到60,所以可以搜索i的所有乘积组合,求出每个组合对应的x,取最小值。

要搜索i的所有乘积组合,需要先对i 进行质数分解,因为i 最大为60,质因数不超过6个。然后就是一个dfs过程,枚举当前层的所有选法,然后把没选的传给下一层,所有数选完后计算一下x,为了让x尽量小,需要把较大的n分配给较小的p

import sys; readline = sys.stdin.readline
read = lambda: [int(x) for x in readline().split()]
alloc = lambda *s: len(s) != 1 and [alloc(*s[1:]) for i in range(int(s[0]) + 2)] or [0] * int(s[0] + 2)

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51]
def get(n):
    i = 2
    arr = []
    
    while i <= n // i:
        if n % i == 0:
            while n % i == 0:
                arr.append(i)
                n //= i
        i+=1
    if n > 1: arr.append(n)
    return arr

S = [float('inf')] * 61; S[0] = 0
cur = 0
def dfs(arr, nums): # dfs搜索所有乘积组合
    n = len(arr)
    if n == 0:
        nums = sorted(nums, reverse=True)
        prod = 1
        for i, v in enumerate(nums):
            prod *= primes[i] ** (v - 1)
        S[cur] = min(S[cur], prod)
        
        return
    for i in range(1, 1 << n):
        new_arr = []
        num = 1
        for j in range(n):
            if i >> j & 1:
                num *= arr[j]
            else:
                new_arr.append(arr[j])
        dfs(new_arr, nums + [num])
for i in range(1, 61):
    cur = i
    dfs(get(i), [])

print(sum(S))

标签:arr,return,gcd,真题,数论,质数,蓝桥,int,x2
From: https://www.cnblogs.com/iku-iku-iku/p/17084466.html

相关文章

  • 数论证明合集
    裴蜀定理定义:设\(a,b\)为不全为零的整数,则存在整数\(x,y\)使得\(ax+by=\gcd(a,b)\)。证明:1.若\(a,b\)中其中一个数为\(0\),则\(\gcd(a,b)=a\)卢卡斯定......
  • 蓝桥杯 求解 01 背包问题
    题目描述实现一个算法求解01背包问题。背包问题的介绍如下:已知一个容量为 total_weighttotalw​eight 的背包,有不同重量不同价值的物品,问怎样在背包容量限制下达到......
  • 蓝桥杯 求解完全背包问题
    题目描述实现一个算法求解完全背包问题。完全背包问题的介绍如下:已知一个容量为totalw​eight 的背包,有不同重量不同价值的物品,问怎样在背包容量限制下达到利益最大化......
  • 第10届蓝桥杯JavaB组省赛
    第10届蓝桥杯JavaB组省赛其他链接第11届蓝桥杯JavaB组省赛-Cattle_Horse第12届蓝桥杯JavaB组省赛-Cattle_Horse第13届蓝桥杯javaB组省赛-Cattle_Horse前言用时......
  • 蓝桥杯-小朋友崇拜圈
    小朋友崇拜圈班里N个小朋友,每个人都有自己最崇拜的一个小朋友(也可以是自己)。在一个游戏中,需要小朋友坐一个圈,每个小朋友都有自己最崇拜的小朋友在他的右手边。求满足条件的......
  • 第11届蓝桥杯JavaB组省赛
    第11届蓝桥杯JavaB组省赛其他链接第12届蓝桥杯JavaB组省赛-Cattle_Horse第13届蓝桥杯javaB组省赛-Cattle_Horse前言用时及分数视频链接:11届蓝桥杯JavaB组省赛实......
  • 蓝桥杯-路径之谜
    问题描述小明冒充X星球的骑士,进入了一个奇怪的城堡,城堡里边什么都没有,只有方形石头铺成的地面。假设城堡地面是nxn个方格,如图所示。  按习俗,骑士要从西北角走......
  • 蓝桥杯-全球变暖
    你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:........##.....##........##...####....###........其中"上下左右"四个方向上连在一起的一片陆......
  • 蓝桥杯-跳跃
    题目 小蓝在一个n行m列的方格图中玩一个游戏。 开始时,小蓝站在方格图的左上角,即第1行第1列。 小蓝可以在方格图上走动,走动时,如果当前在第r行第c列,他不......
  • 1.29数论课笔记
    o.O一、\(O(\sqrt{n})\)判断质数枚举\(\left[2,\sqrt{n}\right]\)中的数,判断是否能整除\(n\),如果都没有则返回\(true\)。为什么不用枚举\(\sqrt{n}\)以上的数:......