SP5971 LCMSUM
官方链接：LCMSUM - LCM Sum 洛谷搬运链接：SP5971 LCMSUM - LCM Sum 题意 有 TTT 次询问，每次询问给定 nnn，求 ∑i=1nlcm(i,n)\sum_{i=1}^n\text{lcm}(i, n) i=1∑nlcm(i,n) 1⩽T⩽3×1051\leqslant T\leqslant 3\times10^51⩽T⩽3×105 1⩽n⩽1061\le
Luogu P2522 [HAOI2011]Problem b
P2522 [HAOI2011]Problem b 题意 给出 NNN 组数据，每组数据有 a,b,c,d,ka, b, c, d, ka,b,c,d,k，求解： ∑x=ab∑y=cd[gcd(x,y)=k]\sum_{x=a}^b\sum_{y=c}^d[\text{gcd}(x,y)=k] x=a∑by=c∑d[gcd(x,y)=k] 1⩽N,k⩽5×1041\leqslant N, k
Luogu P2398 GCD SUM
P2398 GCD SUM 题意 求 ∑i=1n∑j=1ngcd(i,j)\sum_{i=1}^n\sum_{j=1}^n\text{gcd}(i, j) i=1∑nj=1∑ngcd(i,j) 思路 对原式进行一些变换，提取公因式技巧： ∑i=1n∑j=1ngcd(i,j)=∑i=1n∑j=1nId(gcd(i,j))=∑i=1n∑j=1n((φ∗1)(gcd(i,j))=∑i=1n∑j=
莫比乌斯反演
参考：OI-Wike 莫比乌斯反演 前置芝士 引理1 引理1：∀a,b,c∈Z,⌊abc⌋=⌊⌊ab⌋c⌋\forall a, b, c\in \mathbb{Z}, \left\lfloor\frac{a}{bc}\right\rfloor=\left\lfloor\frac{\left\lfloor\frac{a}{b}\right\rfloor}{c}\right\rfloor∀a,b
ABC214
AtCoder Beginner Contest 214 D - Sum of Maximum Weights 题意 给出一颗 NNN 个顶点的树，每条边都具有边权值，定义与顶点有关的二元函数 f(u,v)f(u, v)f(u,v) 为 顶点 uuu 到顶点 vvv 的最短路径上的边权的最大值。 求 ∑i=1N−1∑j=i+1Nf(i,j)\sum_{i=1}^{N-1}\sum_{j=i+1
2017 Korea Daejeon Regional
官网地址 CF地址 补题，(和重做差不多了😂) B - Connect3 题意 给出一个 4×44\times44×4 的网格图，有两个玩家轮流下黑棋和白棋，每次下棋位置必须保证该棋子的下方有一个棋子，也就是堆栈，形式化地说就是，若下在 (i,j)(i, j)(i,j) 处，当且仅当， (i−1,j)(i-1, j)(i−1,j) 处必须有棋子。 若一个玩家获胜，规则类似于五子棋，只是将“五
原根的性质及运用
注： 本文中 (a,b)=gcd(a,b),[a,b]=lcm(a,b)(a,b)=gcd(a,b), [a,b]=lcm(a,b)(a,b)=gcd(a,b),[a,b]=lcm(a,b) 习惯了(*/ω＼*) 阶(指数) 定义 设 (a,m)=1(a, m) = 1(a,m)=1，由欧拉定理知：aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod maφ(m
CF1557
Codeforces Round #737 (Div. 2) D. Ezzat and Grid 题意 给出一个 n⋅109n\cdot 10^9n⋅109 的网格，初始网格上的数字都是0，再给出 mmm 个横向区间该区间上的数字都是1 每个横向区间用 i,l,ri, l, ri,l,r 表示，第 iii 行上列号为 [l,r][l,r][l,r] 上的数字都是1，如 1,3,41, 3, 4