defmerge_sort(arr,l,r): res = [] if l>=r: return mid = (l+r)//2 merge_sort(arr,l,mid) merge_sort(arr,mid+1,r) i,j = l,mid+1 while i<=mid and j<=r: #因为是先添加元素再移动指针，所以这里是<=，结束条件是一方到达终点（终点出也要判断） if arr[i] <= arr[j]: res.append(arr[i]) i+=1#这里要先添加元素，再移动指针 else: res.append(arr[j]) j+=1 if i <= mid: res.extend(arr[i:mid+1]) if j <= r: res.extend(arr[j:r+1]) arr = [x for x in res] return arr
# 记录每个操作对差分数组的贡献 for x1, y1, x2, y2, c in operations: diff[x1][y1] += c diff[x2 + 1][y1] -= c diff[x1][y2 + 1] -= c diff[x2 + 1][y2 + 1] += c
# 通过二维差分还原整个矩阵 for i inrange(1, n + 1): for j inrange(1, m + 1): diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1] grid[i - 1][j - 1] += diff[i][j] # grid是0-based
return grid
n, m, p = map(int, input().split()) grid = [list(map(int, input().split())) for _ inrange(n)] operations = [tuple(map(int, input().split())) for _ inrange(p)]
result = apply_range_add_2d(n, m, grid, operations) for row in result: print(" ".join(map(str, row)))
双指针算法
分为两大类： 指针指向两个序列（归并排序）；指针指向一个序列（对撞指针，快慢指针，滑动窗口）
伪代码模板
j = 0 while i //for i inrange while j<=i and check(i,j): j+=1
核心思想：将两个for 循环的复杂度变成o(n)
滑动窗口
最小/最大区间，最长子串等问题
核心思想： i 在移动的时候，寻找j 的值，可以确定的是，两者是单调的关系，即 i 往右移动的时候，j 也一定最终往右边移动的
最长无重复子序列：一般需要用哈希表
deflongest_subsequence(nums): i,j = 0,0 n = len(nums) max_length = 0 hashmap = {} for i inrange(n): while j <= i and nums[i] in hashmap: j = hashmap[[nums[i]]+1 hashmap[nums[i]] = i max_length = max(max_length,i-j+1) return max_length
和不超过k 的最长子序列
defmax_length_k(nums,k): n = len(nums) i,j = 0,0 sumn = 0 max_l = 0 for i inrange(n): sumn+=nums[i] while j<= i and sumn > k: sumn -= nums[j] j+=1 max_l = max() return max_l
和大于等于k 的最短子数组
def (): min_length = floar("inf") for : while sumn >=k: min_length = #满足条件就更新 sumn -= l-=1 return
关键思想：
while 条件决定何时缩小窗口。
更新长度（max_length 或 min_length）必须正确放置在 while 循环内或外。
更新长度的时机应该与 while 条件的逻辑保持一致，但具体的位置取决于这是最长还是最短子数组问题。
快慢指针
单链表，数组，用于寻找环，去重
删除重复元素
defdelete_repeat(arr): slow,fast = 0,0 while fast < len(arr): if arr[slow] != arr[fast]: slow+=1 arr[slow] = arr[fast] #这两个更新顺序不能变 fast+=1 return slow+1
对撞指针
用于已排列（可排序）的数组的区间问题
位运算
直接一道例题
"""给定一个长度为n的数列,求二进制表示中1的个数 第一行包含整数n ,第二行包含n个整数,表示整个数列""" deflowbit(x): return x&-x defcount_ones(nums): ans = [] for num in nums: count = 0 while num: num -= lowbit(num) #num 每次都减去最后一个1 count+=1 ans.append(count) return ans n = int(input()) nums = list(map(int,input().split())) print(" ".join(map(str,count_ones(nums))))
离散化
特指整数的有序（排序）的离散化
数组中arr[] 中可能有重复的值——> 去重
unique = list(set(arr))
如何算出arr[i] 离散化之后的值 ——>二分求插入位置
def (): i,j = 0,len(arr)-1 while l<r: mid = l+r//2 if mid[i] >= x: r =mid else: l = mid+1 return r(l) + 1#加1 是让其下标从1开始，加不加一看题目要求
第一种方法
import bisect defderect(arr): ans = [] b = list(set(arr)) b.sort() #将b 数组离散化 for num in arr: ans.append(bisect.bisect_left(b,num)) #求在离散化数组中的位置 return ans
第二种方法
defderect(arr): ans = [] b = list(set(arr)) b.sort() value = list(range(len(b))) dic = dict(zip(b,value)) for num in arr: ans.append(dic[x])
例题
#离散化（映射） """假设有一个无限长的数轴,数轴上每个数都是0 现在我们进行n次操作,每次操作将某一位置x上的数加c 接下来,进行m次询问,每次询问包含两个整数l,r,求区间[l,r]中所有数的和 ——> 差分+前缀和？ 第一行包含两个整数n,m 接下来n行,每行包含两个整数x,c 接下来m行,每行包含两个整数l,r 输出： 输出m个整数,表示每个询问的答案 """ import bisect n, m = map(int, input().split()) # 统计每个位置的总增加值 d = {} for _ inrange(n): x, c = map(int, input().split()) if x notin d: d[x] = c else: d[x] += c
# 离散化：去重并排序 alls = sorted(d.keys())
# 构建前缀和数组 pre_sum = [0] * (len(alls) + 1) for i inrange(len(alls)): pre_sum[i+1] = pre_sum[i] + d[alls[i]]
# 处理每个查询 for _ inrange(m): l, r = map(int, input().split()) # 找到左边界（第一个 >= l 的位置） left = bisect.bisect_left(alls, l) # 找到右边界（最后一个 <= r 的位置） right = bisect.bisect_right(alls, r) - 1 if left > right: print(0) else: print(pre_sum[right + 1] - pre_sum[left])
区间合并
将所给区间，按照左端点为基准排序
维护一个当前值 st,ed 循环时候更新
defmerge_intervals(intervals): ifnot intervals: return0 intervals.sort(key = lambda x : x[0] ) #X代表每一个元素 ： X[0] 取左端点为排序依据 count = 0 st,en = intervals[0] for s,e in intervals[1:]: if s<= en: en = max(en,e) else: count +=1 st,en = s,e return count+1#最后一个区间没有被统计 a = int(input()) n = [tuple(map(int,input().split())) for _ inrange(a)] print(merge_intervals(n))
数据结构
链表(静态数组的实现)
idx的作用
作为新结点的存储索引，保证将数据存到正确的位置
每次新增节点都要将idx知道空位，自增
单链表
e = [0]*1010 ne = [0]*1010 head = -1 idx = 0 cnt = 0
#获取index位置的值 defget(index): global head,e,ne,cnt if index < 0or index > cnt: return -1 i = head for _ inrange(index): i = ne[i] return e[i] #在头节点插入 defaddAtHead(val): global idx,e,ne,head,cnt e[idx] = val ne[idx] = ne[head] head = idx idx+=1 cnt+=1 #在index的前一个位置插入 defaddAtIndex(index,val): global idx,e,ne,head,cnt if index > cnt: return if index <=0: addAtHead(val) return i = head for _ inrange(index-1): i = ne[i] e[idx] = val ne[idx] = ne[i] ne[i] = idx idx +=1 cnt+=1 #在尾部加入节点 defaddAtTail(val): addAtIndex(cnt,val) return
#将index的值删除 defdeleteAtIndex(index,val): global ... if index ==0: head = ne[head] #直接更新head return if index >= cnt or index < 0: return i = head for _ inrange(index-1): i = ne[i] ne[i] = ne[ne[i]]
双链表
在向头节点插入元素的时候，需要注意的是原来链表中是否有值
以及删除的时候，需要注意删除的元素是否为最后一个元素
e = [0]*1010 ne = [-1]*1010 prev = [-1]*1010 head = -1 tail = -1 idx = 0 cnt =0
栈
单调栈
处理下一个更大或者更小元素
最近更小/更大
直方图最大矩形面积
接雨水
有效括号
递增，元素从底到顶，依次递增（删除比当前元素大的值）
defmonotonic_stack(arr): stack = [] res = [] #用来存储当前栈的变化 for x in arr: while stack and stack[-1] > x: #如果栈顶元素大于当前元素，那么栈顶元素出栈，该元素入栈 stack.pop() stack.append(x) res.append(stack[:]) return res
找左边第一个小于当前值的元素
栈储存的是下标
从左向右遍历，维护栈中对应元素是递增的
当遇到一个小于栈顶的元素，出栈，（栈为非空）那么此时的栈顶元素就是该元素左边第一个小的值
deffind_left_first_min(arr): n = len(arr) stack = [] res = [-1]*n for i inrange(n): while stack and arr[stack[-1]]> arr[i]: stack.pop() if stack: res[i] = arr[stack[-1]] stack.append(i) return res
找右边第一个大于当前值的元素
栈储存下标
从左开始遍历，维护栈中其对应递减
当遇到一个大于当前栈顶的元素，出栈，且这个元素就是当前栈顶最右边第一个大的值
deffind_right_first_max(arr): stack = [] res = [] for i inrange(len(arr)): while stack and arr[stack[-1]] < arr[i]: res[stack.pop()] = arr[i] stack.append(i) return res
有的题目可能问的是，距离
右边res [stack.pop()] = (i-stack.pop())
左边res[i] = i - stack[-1]
还要注意res 的初始化
队列
单调队列
适用于滑动窗口
滑动窗口最大值
滑动窗口最小值
最短子数组和>=k
#单调队列 defmonotonic_queue(arr): from collections import deque q = deque() res = [] for x in arr: while q and q[-1] > x: # 🔹 确保队列单调递增 q.pop() q.append(x) res.append(list(q)) # 记录每一步的队列状态 return res
#滑动窗口最大值 """给定一个数组nums ,和窗口大小k,找到每个窗口中的最大值 用固定长度的队列来维护固定长度的数组 要找最大值,将队列维护成递减,那么每个恒定长度的队列中,对首元素就是最大值 """ from collections import deque defmax_sliding_window(nums,k): d = deque() res = [] n = len(nums) for i inrange(n): while d and nums[d[i]] < nums[i]: d.pop() #维护递减 d.append(i) #如果当前对长度大于k,那么队首元素出队 if i-d[0]>=k: d.popleft() #当i大于等于k-1时，记录答案 if i >= k-1: res.append(nums[d[0]]) return res nums = [1,3,-1,-3,5,3,6,7] k = 3 print(max_sliding_window(nums,k)) """ [3,-1] [3] [3,-1,-3] [3,3] [5] [3,3,5] [5,3] [3,3,5,5] [6] [3,3,5,5,6] [7] [3,3,5,5,6,7] """
defprefix_function(s): n = len(s) pi = [0]*n j = 0 for i inrange(n): #不匹配 while j > 0and s[j]!=s[i]: j = pi[j-1] #匹配，更新j if s[j]==s[i]: j+=1 #记录 pi[i] = j
deffind_occurrence(s,p): cur = s+'#'+p lps = prefix_function(cur) res = [] sz1,zsz2 = len(p),len(p) for i inrange(sz2+1,sz1+sz2+1): if lps[i] == sz2: res.append(i-2*sz2) return res
i循环的区间： s 的结尾下标：sz2-1 ；# 下标：sz2 ； p 的起始下标：sz2+1
在 文本串中所匹配的下标：i - (sz2) -(sz2+1) + 1 = i-2*sz2
经典写法(与前缀函数写法类似)
这时的j 相当于指针——> 对应下标
defkmp(s,p): pi = prefix_function(p) #模式串的前缀函数 n1 ,n2 = len(s),len(p) res = [] j = 0#模式串的当前匹配位置 for i inrange(n1): #不匹配：j 回退 while j >0and s[i] !=p[j]: j = pi[j-1] #匹配 ；j+=1 if s[i] == p[j]: j+=1 #当找到一个完全匹配的记录 if j == n2: # j == n2 而不是j == n2-1 因为当最后一位匹配（j = n2-1），j+=1 ——> j == n2 res.append(i-n2+1) #记录起始位置 j = pi[j-1] #继续匹配 return res
TRIE树（字典树）
高效存储和查找字符串的数据结构
son[p] 可以存储每个节点所包含的多个（>=0）字母对应的数字u， u = ord(c)-ord('a')``son[p][u] 存储的是下一个节点的信息。或者认为 二维数组存储的是每个字母的不同映射
cnt 将其看作标志也可以 ，如果是0 那么没有以这个为前缀的值，相反则有，数值为几就有几个
idx 记录字典树的总结点的个数
n = 10010 son = [[0]*26for _ inrange(n)] idx = 0 cnt = [0]*n
#插入操作 definsert(s): global inx p = 0#从根节点开始 for c in s: u = ord(c) - ord('a') if son[p][u] ==0: idx+=1 son[p][u] = idx p = son[p][u] cnt[p] +=1 #查找操作 defsearch(s): p = 0 for c in s: u = ord(c) - ord('a') if son[p][u] == 0: returnFalse p = son[p][u] return cnt[p] >0
defdsu(n,pairs): pa = list(range(n)) for p in pairs: if p[0] == 'Mab': union(p[1],p[2],pa) else: if find(p[1],pa) == find(p[2],pa): print('YES') else: print('NO') deffind(x,pa): if pa[x]!=x: pa[x] = find(pa[x],pa) return pa[x]
definin_heap(arr): n=len(arr) for i inrange(n//2-1,-1,-1): down(i,arr,n)
down(i,arr,size)
defdown(i,arr,size): whileTrue: mini = i left = i*2+1 right = i*2+2 if l < size and arr[i] >= arr[left]: mini = left if r < size and arr[i] >= arr[right]: mini = right if i = mini : #这一步不要忘记了 break arr[i],arr[mini] = arr[mini],arr[i] i = mini
up(i,arr,size)
defup(i,arr,size): whileTrue: parent = (i-1)*2 if parent >= 0and arr[parent] > arr[i]: arr[parent],arr[i] = arr[i],arr[parent] i = parent else: break
defheap_sort(arr): n = len(arr) for i inrange(n//2-1,-1,-1): down(i,arr,n) #将堆顶元素与堆尾元素互换，维护最大堆 for i inrange(n-1,-1,-1): arr[0],arr[i] = arr[i],arr[0] down(0,arr,i) #堆的范围是递减的，只处理剩下的部分 defdown(i,arr,size): #维护大顶堆 whileTrue: maxi = i left = i*2+1 right = i*2+2
if left < size and arr[maxi] < arr[left]: maxi = left if right < size and arr[maxi] < arr[right]: maxi = right if maxi == i: break arr[maxi],arr[i] = arr[i],arr[maxi] i = maxi arr = [5,3,8,4,2,6,1] heap_sort(arr)
for _ in range(n): arr[0],arr[-1]= arr[-1],arr[0] down(0,arr,n) 与之对比，改写法没有动态更改堆的大小，已排序的部分仍然会被影响
#升序 import heapq defheap_sort(arr): heapq.heapify(arr) return [heapq.heappop(arr) for _ inrange(5)]
#降序 import heapq defheap_sort(arr): arr = [-x for x in arr] heapq.heapify(arr) return [-heapq.heappop(arr) for _ inrange()]
哈希表
普通实现
k = (x%mod+mod)%mod
拉链法
h[k] 初始值都为-1 ,相当于单链表中的head用于储存每个桶里面的头节点
e[],ne[] 用来当作链表，需要注意的是，在插入操作，每次都相当于从头节点插入新节点
mod = 100010 ne =[0]*mod e = [0]*mod h = [-1]*mod idx = 0
definsert(x): k = (x%mod+mod)%mod e[idx] = x ne[idx] = h[k] #ne[idx] = head h[k] = idx #head = idx idx+=1 deffind(x): k = (x%mod+mod)%mod i = h[k] while i != -1: if e[i] == x: returnTrue else: i = ne[i] returnFalse
开放寻址法
mod = 200020 h = [-1]*mod
definsert(x): k = (x%mod+mod)%mod while h[k] != -1and h[k]!= x: k = (k+1)%mod h[k] = x deffind(x): k = (x%mod+mod)%mod while h[k] != -1: if h[k] != x: k = (k+1)%mod else: returnTrue returnFalse
defsolve_n_q(n): defdfs(row,cols,dg,udg,board,res): n = len(board) if row == n: res.append(["".join(row) for row in board]) return #在当前行中，递归所有的列 for col inrange(n): if col in cols or (row-col) in dg or (row+col) in udg : continue board[row][col] = "Q" cols.add(col) dg.add(row-col) udg.add(row+col) dfs(row+1,cols,dg,udg,board,res) #回溯，撤销选择 board[row][col] ="." cols.remove(col) dg.remove(row-col) udg.remove(row+col)
board = [["."]*n for _ inrange(n)] res = [] dfs(0,set(),set(),set(),board,res) return res
n = int(input()) res = solve_n_q(n) for i in res: print(i)
defbfs_maze(maze): queue = deque([(0,0,0)]) #注意这里是传递一个列表，列表里面第一个值(0，0，0) n,m = len(maze),len(maze[0]) directions = [(1,0),(-1,0),(0,1),(0,-1)] prev = {} while queue: x,y,step = queue.popleft() #到达终点的操作 if (x,y) == (n-1,m-1): path = [] while (x,y) in prev: path.append((x,y)) x,y = prev[(x,y)] path.append((0,0)) path.reverse()
for i in path: print(i) print(step) return #没到终点，寻找下一个点 for dx,dy in directions: nx,ny = x+dx,y+dy if0<=nx<n and0<=ny<m and maze[nx][ny] ==0and (nx,ny) notin prev: queue.append((nx,ny,step+1)) prev[(nx,ny)] = (x,y) print(-1)
#bfs 拓扑排序 """给定一个n个点m条边的有向图,图中可能存在重边和自环 请输出任何一个该有向图的拓扑序列,如果拓扑序列不存在，输出-1 若一个由图中所有点构成的序列A满足,对于每个边,(x,y) 在A中x出现在y之前 则称A是该图的一个拓扑序列 第一行包含两个整数n,m 接下来的m行,每行包含两个整数x,y,表示存在一条从x到y的有向边 输出一个拓扑序列,如果不存在拓扑序列,输出-1 """ from collections import deque n,m = map(int,input().split()) e = [0]*m ne = [-1]*m h = [-1]*(n+1) idx = 0 st = [False]*(n+1) in_degree = [0]*(n+1) edge_set = set() #创建有向图 defadd(a,b): global idx if (a,b) in edge_set: return e[idx] = b ne[idx] = h[a] h[a] = idx idx+=1 in_degree[b]+=1 edge_set.add((a,b)) deftopsort(): queue = deque() res = [] #让所有度数为0的入队 for i inrange(1,n+1): if in_degree[i] == 0: queue.append(i)
while queue: u = queue.popleft() res.append(u) i = h[u] while i != -1: j = e[i] in_degree[j] -=1 if in_degree[j]== 0: queue.appen(j) i = ne[i] iflen(res)== n: print(" ".join(map(str,res))) else: print(-1) for _ inrange(m): a,b = map(int,input().split()) add(a,b) topsort()
defbellmen_ford(n,edge,start,k): INF = float("inf") dist = [INF]*(n+1) dist[start] = 0 #进行k条边的松弛操作，注意要进行备份 for _ inrange(k): backup = dist[:] #注意备份 for a,b,w in edge: if backup[a] != INF: dist[b] = min(dist[b],backup[a]+w) return dist[n] if dist[n] != INF else -1
spfa 算法（负权）（链式前向星）
是对bellman-ford 算法的队列优化，有时候我们不需要那么多的松弛操作
维护一个队列，里面的值都是必要进行松弛操作的点——> 通过队列来进行更新
当一个节点符合条件dist[j] > dist[u]+w
场景1：节点 j 不在队列中 → 更新距离并加入队列。
场景2：节点 j 已在队列中 → 仅更新距离，不入队（避免重复处理）
from collections import deque
n,m = map(int,input().split()) e = [0]*m ne = [-1]*m h = [-1]*(n+1) idx = 0 weight = [0]*m
defadd(a,b,w): global idx e[idx] = b ne[idx] = h[a] weight[idx] = w h[a] = idx idx+=1 defspfa(n,start): INF = float("inf") dist = [INF]*(n+1) queue = deque() queue.append(start) dist[start] = 0 in_queue = [False]*(n+1) while queue: u = queue.popleft() in_queue [u] = True i = h[u] while i != -1: j = e[i] w = weight[i] if dist[j] > dist[u]+w: dist[j] = dist[u]+w ifnot in_queue[j]: queue.append(j) in_queue(j) = True i = ne[i] return dist[n]
spfa 也能适用于全为正权的题目中，代替dijkstra 算法
如果要检测是否有负权环
from collections import deque
INF = float('inf') n,m = map(int,input().split()) h = [-1]*(n+1) e = [0]*m ne = [-1]*m weight = [0]*m #记录权重 idx = 0 defadd(a,b,w): global idx e[idx] = b ne[idx] = h[a] weight[idx] = w h[a] = idx idx+=1 defspfa(n,start): cnt =[0]*(n+1) dist = [INF]*(n+1) in_queue = [False]*(n+1) in_queue[start] = True dist[start] = 0 queue = deque() #初始化队列 queue.append(start) while queue: u = queue.popleft() in_queue[u] = False i = h[u] while i != -1: j = e[i] w = weight[i] if dist[j] > dist[u]+w: #就算是在队列中，也要更新 dist[j] = dist[u]+w ifnot in_queue[j]: queue.append(j) in_queue[j] = True cnt[j] = cnt[u]+1#只有在新元素入队的时候更新cnt if cnt[j] > n : return"负权环存在" i = ne[i] return dist[n] if dist[n] != INF else"impossible" for _ inrange(m): u,v,w = map(int,input().split()) add(u,v,w) print(spfa(n,1))
数论
质数
分解质因数（base）
埃氏筛法
#埃氏筛法求质数 """给定一个正整数n求出1——n 中的所有质数的个数""" deffind_prime(n): is_prime = [True]*(n+1) is_prime[0]=is_prime[1]=False for i inrange(2,int(n**0.5)+1): if is_prime[i]: for j inrange(i*i,n+1,i): is_prime[j] = False return [i for i inrange(2,n+1) if is_prime[i]]
线性筛法
#线性筛质数（空列表中添加质数） defliner_prime(n): is_prime = [True]*(n+1) prime = [] for i inrange(2,n+1): if is_prime[i]: prime.append(i) for p in prime: if i*p > n : break is_prime[i*p] = False if i%p == 0: """ i%p == 0 意味着i 之前被p 筛选过了 由于p在列表中是由小到大排列的,此时i的最小质因子就是p, i 乘以其他列表中的指数也一定会被p给筛掉 比如 4 %2 ==0 , [2,3]就不需要将p循环到3 再去筛选12 了直接break """ break return prime
约数
试除法求约数
#试除法求约数 """给定n个正整数ai,对于每个ai 求出他的所有约数""" deffind_divisions(n): small_divisions = [] big_divisions = [] for i inrange(1,int(n**0.5)+1): if n%i == 0: small_divisions.append(i) if i!= n//i : big_divisions.append(n//i) return small_divisions + big_divisions[::-1]
defprint_number(numbers): for number in numbers: divisions = find_divisions(number) print(str(divisions))
if __name__ == "__main__": numbers = list(map(int, input().split())) print_number(numbers)
defprime_factors(n): factor = {} if n == 1: return factor while n%2 == 0: if2notin factor : factor[2] = 0 factor[2] += 1 n//=2 #偶数处理完之后，仅仅剩余奇数。 p = 3 while p*p <= n: while n%p == 0: if p notin factor: factor[p] = 0 factor[p] += 1 n//=p p+=2 #当不符合循环条件（即为 p*p >n，且当前n 大于1），此时的n也是质数 if n > 1: factor[n] = 1 return factor #统计最终的指数（同样用哈希表） defcount_divisiors(numbers): prime_count = {} for num in numbers : factors = prime_factors(num) for key,value in factors.items(): if key notin prime_count: prime_count[key] = 0 prime_count[key] += value n = 1 for value in prime_count.values(): n *= (value + 1) return n%(10**9+7)
if __name__ == "__main__": numbers = [] whileTrue: try: number = int(input()) numbers.append(number) except ValueError: break print(count_divisiors(numbers))
约数之和
#求约数的和 """给出n个正整数ai,求出这些数的乘积的约数的和"""
#正整数质因子分解，并将其储存在字典中
defprime_factors(n): factor = {} if n == 1: return factor while n%2 == 0: if2notin factor : factor[2] = 0 factor[2] += 1 n//=2 #偶数处理完之后，仅仅剩余奇数。 p = 3 while p*p <= n: while n%p == 0: if p notin factor: factor[p] = 0 factor[p] += 1 n//=p p+=2 #当不符合循环条件（即为 p*p >n，且当前n 大于1），此时的n也是质数 if n > 1: factor[n] = 1 return factor
defcount_divisiors(numbers): # 统计每个数的因子个数 divisiors = {} for num in numbers: factors = prime_factors(num) for key,value in factors.items(): if key notin divisiors: divisiors[key] = 0 divisiors[key] += value s = 1 for key,value in divisiors.items(): s*=geometric_sequence(key,value) return s%(10**9+7)
if __name__ == "__main__": numbers = [] whileTrue: try: number = int(input()) numbers.append(number) except ValueError: break print(count_divisiors(numbers))
欧拉函数
欧拉定理
#欧拉函数 """求正整数n的欧拉函数的值""" defeuler_function(n): ans = n for i inrange(2,int(n**0.5)+1): if n%i == 0: ans *= (1 - 1/i) while n%i == 0: n//=i if n > 1: ans *= (1 - 1/n) returnint(ans) defevery_euler_function(numbers): for number in numbers: print(euler_function(number)) if __name__ == "__main__": numbers = [] whileTrue: try: line = input().strip() # 去除首尾空白字符 ifnot line: # 如果是空行就退出 break number = int(input()) numbers.append(number) except ValueError: break every_euler_function(numbers)
筛法求欧拉函数
#筛法求多个数的欧拉函数 """给一个正整数N ,求出1-N 中每个数的欧拉函数之和""" deflinear_euler_function(n): #储存初始的欧拉函数值 phi = list(range(n+1)) is_prime = [True]*(n+1) prime = [] for i inrange(2,n+1): if is_prime[i]: prime.append(i) phi[i] = i-1 for p in prime: if i*p > n : break is_prime[i*p] = False if i%p==0: phi[i*p] = phi[i]*p break#不需要在检查其他的p else: phi[i*p] = phi[i]*(p-1) returnsum(phi)
快速幂
快速幂（迭代递归）
#快速幂
#递归版本的快速幂 求解a^b defbinpow(a, b): if b == 0: return1 res = binpow(a, b//2) if b % 2 == 0: return (res * res) else: return (res * res * a) #迭代版本的快速幂 # b & 1 检查当前位是否为1 # b >>= 1 将b右移一位，相当于b = b // 2 defbinpow(a,b): res =1 while b >0 : if b & 1: res = res*a a= a*a b>>=1 return res
#模意义下取幂——> 将每个值都进行取模运算 """计算x^n mod m"""
defbinpow(a,b,m): res = 1 a%=m #确保初始值在合理范围中 while b > 0: if b&1: res = res*a%m #防止中间结果溢出 a = a*a%m b>>=1 return res defbinpow(a, b, p): if b == 0: return1 res = binpow(a, b//2, p) if b % 2 == 0: return (res * res) % p else: return (res * res * a) % p
快速幂求逆元
#快速幂求逆元 """给出N组ai pi, 其中pi 是质数（要用到费马定理） 求ai 模pi 的逆元""" defbinpow(a,b,p): res = 1 a%=p #确保初始值在合理范围中 while b > 0: if b&1: res = res*a%p #防止中间结果溢出 a = a*a%p b>>=1 return res defbinpow(a, b, p): if b == 0: return1 res = binpow(a, b//2, p) if b % 2 == 0: return (res * res) % p else: return (res * res * a) % p definverse_mod(numbers): for number in numbers : a,p = number[0],number[1] if number[0]%number[1]!=0: # p=2 的时候应该也为 impossible print(binpow(a,p-2,p)) else: print("impossible") if __name__ == "__main__": numbers = [] whileTrue: try: """ 使用strip去除首尾空白字符 检查是否有空白行 检查是否有两个数字 将字符串转换为数字 line = input().strip() if not line : break a , p = map(int,line.aplit()) numbers.append([a,p]) """ line = input().strip() ifnot line : break#如果是空行就退出 number = line.split() number.append([int(number[0]),int(number[1])]) except ValueError: break inverse_mod(numbers)
拓展欧几里得算法
#拓展欧几里得算法 """给出n组正整数ai bi,求出每组ai bi对应的xi , yi 使得ai*xi + bi*yi = gcd(ai,bi)""" defextend_gcd(a,b): if b== 0: return a,1,0# 当在python 中用逗号分隔多个值的时候，python 会自动将之打包成一个元组 gcd,x1,y1 = extend_gcd(b,a%b) x = y1 y = x1- (a//b)*y1 return gcd,x,y
