定义 若 ax\equiv 1\pmod{p},则称 x 为 a 关于 p 的逆元,记作 a^{-1} 逆元存在的充要条件:a,p 互质,即 \mathrm{gcd}(a,p)=1 求解 exgcd求逆元 由于同余方程 …
【学习笔记】二元一次不定方程(exgcd)
定义 二元一次不定方程的形式为:ax+by=c,与同余方程 ax\equiv c\pmod{b} 等价 扩展欧几里得算法(exgcd) 该算法用于求解形如 ax+by=\mathrm{gcd}(a,b) 的不定方程 当 …
Codeforces 1367F1 Flying Sort (Easy Version)【枚举下限 二分上限】
题目 This is an easy version of the problem. In this version, all numbers in the given array are distinct and th…
Codeforces 1370E Binary Subsequence Rotation
题目 Naman has two binary strings s and t of length n (a binary string is a string which only consists of the ch…
【模板】网络流 Dinic算法
每次增广前,先bfs将图分层,然后不断dfs增广 两个优化: 多路增广 当前弧优化 时间复杂度: 一般图:O(n^2 m) 容量均为1的图:O(min\lbrace m^{\frac{3}{2}} ,n^{\frac{2…
Codeforces 1373E Sum of Digits【构造】
题目 Let f(x) be the sum of digits of a decimal number x. Find the smallest non-negative integer x such that f(x…
Codeforces 1336A Linova and Kingdom【贪心】
题目 Writing light novels is the most important thing in Linova's life. Last night, Linova dreamed about a fanta…
Codeforces 1343E Weights Distributing【分配边权的两段最短路】
题目 You are given an undirected unweighted graph consisting of n vertices and m edges (which represents the map…
【模板】主席树/可持久化线段树(Luogu P3834)
传送门:Luogu P3834 【模板】可持久化线段树 1(主席树)(静态区间第k小) #include <iostream> #include <stdio.h> #include <string.h…