wty's blog

问题描述 nnn 个编号从 1,⋯ ,n1, \cdots, n1,⋯,n 的人逆时针站成一圈，开始从 111 号开始，每次从当前人开始数 kkk 个，然后这个人出局，求最后一个人编号多少？ 该问题由约瑟夫 (Titus Flavius Josephus)，于公元一世纪提出，他当时求解的是 n=41,k=2n=41, k=2n=41,k=2 的情况 (maybe (oﾟvﾟ)ノ 但他还是很强

反素数 定义 “反素数”(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

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

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 的路程小于等于

AtCoder Beginner Contest 212 E - Safety Journey 题意 给出一个含有 N(N⩽5000)N(N\leqslant 5000)N(N⩽5000) 个顶点的完全图，编号从1到N，从中删去 M(M⩽5000)M(M\leqslant 5000)M(M⩽5000) 条边，要求每次从1号顶点出发，经过 K(K⩽5000)K(K\leqslant 5000)K

AtCoder Beginner Contest 213 E - Stronger Takahashi 题意 给出一个迷宫: .代表可以走的道路，#代表墙，你可以花费一点力气打破任意一个 2×22\times 22×2 区域中的所有的墙 请问从迷宫的左上角走到右下角，最少要花费多少力气？ 思路 这道题相比F题要水多了，但我并没看出来 这题可以相当于建图跑最短路，但由于图上的边权只有0和1，所

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

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

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

注： 本文中 (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