CF1559 - E. Mocha and Stars
E. Mocha and Stars 题意 给出 nnn 个区间 [li,ri][l_i, r_i][li,ri] 和 mmm，保证 li⩽ri⩽ml_i\leqslant r_i\leqslant mli⩽ri⩽m，求： ∑a1=l1r1∑a2=l2r2⋯∑an=lnrn[gcd(a1,a2,…,an)=1]⋅[a1+a2+⋯+an⩽m]\sum_{a_1=l_1}^{r_1}\sum
Luogu P1829 [国家集训队]Crash的数字表格 / JZPTAB
P1829 [国家集训队]Crash的数字表格 / JZPTAB 题意 给出 n,mn, mn,m 求解： ∑i=1n∑j=1mlcm(i,j)\sum_{i=1}^n\sum_{j=1}^m\text{lcm}(i, j) i=1∑nj=1∑mlcm(i,j) 1⩽n,m⩽1071\leqslant n, m\leqslant 10^71⩽n,m⩽107 思路 对原式进行数论变换： ∑i
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) 处必须有棋子。 若一个玩家获胜，规则类似于五子棋，只是将“五