最近尝试使用Python打下算法题，记录下需要注意的地方吧。 使用main()函数 这样的习惯就和c++一样了，这样的好处在于如果其他文件中 import ，使用该文件中的函数，不会运行其主函数部分。 def main(): pass if __name__ == "__main__": main() 全局变量的问题 ans = 0 def main(): ans += 1 这样

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

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

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

反素数 定义 “反素数”(antiprime number)也称为“高合成数”(highly composite number)。 设 τ(n)=∑d∣n1\tau(n)=\sum_{d|n} 1τ(n)=∑d∣n​1，表示 nnn 的所有因数个数。 若正整数 qqq 满足：对于 ∀x∈Z⩾1,x<q\forall x\in\mathbb Z_{\geqslant 1},x < q

P3953 [NOIP2017 提高组] 逛公园 总算把咕了快四年的题A了QAQ。 题意 给出 N,M,K,PN, M, K, PN,M,K,P，一个包含 NNN 个点 MMM 条边的有向图，没有自环和重边，顶点编号从 1∼N1\sim N1∼N。 令 dis(u,v)dis(u, v)dis(u,v) 为从 uuu 出发到达 vvv 的最短路径，求从顶点 111 到顶点 NNN 的路程小于等于

POJ 2886: Who Gets the Most Candies? POJ 2886: Who Gets the Most Candies? 题意 约瑟夫环问题(Josephus Problem)(固定下一个踢出位置)，这道题下一个踢出位置由当前踢出人决定。 NNN 个人围成一圈，编号从 1∼N1\sim N1∼N，每个当前踢出的人能决定下一个踢出的人在相对于他的第几个位置，开始时踢出人

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