AtCoder Beginner Contest 215 E - Chain Contestant 题意 给出一个由 101010 种大写字母 A∼JA\sim JA∼J 组成的字符串 SSS，长度为 NNN，求 SSS 有多少个下标序列满足下列条件： 令下标序列所对应的 SSS 的子序列为 TTT，满足同一种字母在 TTT 中都是连续出现的，如：AAABBCCC 满足条件，但 AABBACC

AtCoder Regular Contest 125 B - Squares 题意 给出一个 NNN，求有多少对 (x,y)(x,y)(x,y) 满足如下条件： 1⩽x,y⩽N1\leqslant x, y\leqslant N1⩽x,y⩽N。 x2−yx^2-yx2−y 是一个平方数。（规定 000 也是平方数） 答案对 998244353998244353998244353

D2. Mocha and Diana (Hard Version) 题意 给出两个森林，两个森林中的点编号都是从 1…n1\ldots n1…n，第一个森林中有 m1m_1m1​ 条边，第二个森林中有 m2m_2m2​ 条边，可以进行连边操作，每次对两个森林中的顶点 (u,v)(u, v)(u,v) 进行连边，并要求每次连边之后两个都仍是森林（即不会出现环，注：一棵树也是森林），求最多能连多少

P5176 公约数 题意 有 TTT 组数据，每组数据给出，n,m,pn, m, pn,m,p，求： ∑i=1n∑j=1m∑k=1pgcd(i⋅j,i⋅k,j⋅k)×gcd⁡(i,j,k)×(gcd⁡(i,j)gcd⁡(i,k)×gcd⁡(j,k)+gcd⁡(i,k)gcd⁡(i,j)×gcd⁡(j,k)+gcd⁡(j,k)gcd⁡(i,j)×gcd⁡(i,k))\sum_{i=1}^n\sum

P3327 [SDOI2015]约数个数和 题意 有 TTT 组数据，每组数据给出 n,mn, mn,m，求解 ∑i=1n∑j=1md(ij)\sum_{i=1}^n\sum_{j=1}^md(ij) i=1∑n​j=1∑m​d(ij) 其中 d(n)=∑i∣n1d(n)=\sum_{i|n}1d(n)=∑i∣n​1，即为 nnn 的约数个数。 数据范围：1⩽T,n,m⩽5×1041\leqsl

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

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∑n​j=1∑m​lcm(i,j) 1⩽n,m⩽1071\leqslant n, m\leqslant 10^71⩽n,m⩽107 思路 对原式进行数论变换： ∑i

官方链接：LCMSUM - LCM Sum 洛谷搬运链接：SP5971 LCMSUM - LCM Sum 题意 有 TTT 次询问，每次询问给定 nnn，求 ∑i=1nlcm(i,n)\sum_{i=1}^n\text{lcm}(i, n) i=1∑n​lcm(i,n) 1⩽T⩽3×1051\leqslant T\leqslant 3\times10^51⩽T⩽3×105 1⩽n⩽1061\le

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∑b​y=c∑d​[gcd(x,y)=k] 1⩽N,k⩽5×1041\leqslant N, k

P2398 GCD SUM 题意 求 ∑i=1n∑j=1ngcd(i,j)\sum_{i=1}^n\sum_{j=1}^n\text{gcd}(i, j) i=1∑n​j=1∑n​gcd(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=