wty's blog

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

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

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=

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

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

官方链接：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