凌乱之风

数论题

AcWing寒假每日一题(41) codeforces(52) VJ比赛(10) 其他(3) 数据结构题(3) 算法(43) 题解(1)

/ 注册

全部文章 / 数论题（共14篇）

[HAOI2011] problem b (莫比乌斯反演)

题意：求 ∑ i = a b ∑ j = c d [ gcd ⁡ ( i , j ) = k ] \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k] i=a∑bj=c∑d[gcd(i,j)=k] 分析：用二维前缀和的思想，把答案分为 4 4 4个部分 ...

2021-11-06

0 279

[SDOI2015] 约数个数和 (莫比乌斯反演)

题意：设 d ( x ) d(x) d(x) 为 x x x 的约数个数，求 ∑ i = 1 N ∑ j = 1 M d ( i j ) \sum_{i=1}^{N}\sum_{j=1}^{M} d(ij) i=1∑Nj=1∑Md(ij) 分析：首先 i = p 1 α 1 ...

2021-11-06

0 232

[NOI2010] 能量采集 (莫比乌斯反演欧拉反演)

题意：求 2 ∗ ∑ i = 1 n ∑ j = 1 m gcd ⁡ ( i , j ) − n ∗ m 2*\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)-n*m 2∗i=1∑nj=1∑mgcd(i,j)−n∗m 分析：莫比乌斯反演：那么只需要求 ...

2021-11-06

0 351

[洛谷 P1891] 疯狂 LCM (欧拉函数莫比乌斯反演)

题意：求 ∑ i = 1 n lcm ( i , n ) \sum_{i=1} ^{n} \text{lcm}(i,n) i=1∑nlcm(i,n) 分析：法一：欧拉函数拆一下 lcm ( i , n ) = i ⋅ n gcd ⁡ ( i , n ) \text{lcm}(i...

2021-11-06

0 330

[洛谷 P3768] 简单的数学题 (莫比乌斯反演狄利克雷卷积杜教筛)

题意：求 ∑ i = 1 n ∑ j = 1 n i j gcd ⁡ ( i , j ) \sum_{i=1}^{n}\sum_{j=1}^{n}ij\gcd(i,j) i=1∑nj=1∑nijgcd(i,j) 对 p p p 取模， n ≤ 1 0 10 , 5 × 1 0 8 ≤...

2021-11-06

0 568

[2019 CCPC网络赛] huntian oy (杜教筛)

题意 T T T 组输入，给定 n , a , b n,a,b n,a,b 求 f ( n , a , b ) = ∑ i = 1 n ∑ j = 1 i gcd ⁡ ( i a − j a , i b − j b ) [ gcd ⁡ ( i , j ) = 1 ] f(n,a,b)=\s...

2021-11-06

0 351

[洛谷 P4318] 完全平方数 (杜教筛)

题意 T T T 组询问，回答第 K i K_i Ki 个不是完全平方数的正整数倍的数。 1 ≤ K i ≤ 1 0 9 , T ≤ 50 1\le K_i \le 10^9,T \le 50 1≤Ki≤109,T≤50 分析：法一：如果一个数 n n n 不是完全平方数，...

2021-11-06

0 291

[2019 icpc西安邀请赛] Product (莫比乌斯反演杜教筛)

题意求 ∏ i = 1 n ∏ j = 1 n ∏ k = 1 n m gcd ⁡ ( i , j ) [ k ∣ gcd ⁡ ( i , j ) ] m o d p \prod_{i=1} ^{n} \prod_{j=1}^{n}\prod_{k=1}^{n}m^{\gcd(i,j...

2021-11-06

0 316

[洛谷 P6055] [RC-02] GCD (莫比乌斯反演杜教筛)

题意求 ∑ i = 1 n ∑ j = 1 n ∑ p = 1 ⌊ n j ⌋ ∑ q = 1 ⌊ n j ⌋ [ gcd ⁡ ( i , j ) = 1 ] [ gcd ⁡ ( p , q ) = 1 ] \sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{p=1}^{\l...

2021-11-06

0 245

[2018 icpc徐州网络赛] Easy Math (杜教筛)

题意求 ∑ i = 1 m μ ( i n ) \sum_{i=1}^{m} \mu(in) i=1∑mμ(in) m ≤ 2 × 1 0 9 , n ≤ 1 0 12 m \le 2×10^9,n\le 10^{12} m≤2×109,n≤1012 分析：首先分析 n n n...

2021-11-06

0 397