凌乱之风
凌乱之风
全部文章
分类
AcWing寒假每日一题(41)
codeforces(52)
VJ比赛(10)
其他(3)
数据结构题(3)
数论题(15)
算法(43)
题解(1)
归档
标签
去牛客网
登录
/
注册
凌乱之风的博客
欢迎来到凌乱之风的博客qwq
全部文章
(共30篇)
[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
BSGS、exBSGS
BSGS (Baby Step Giant Step) : \text{BSGS (Baby Step Giant Step)}: BSGS (Baby Step Giant Step): 给定正整数 a , b , p , a ⊥ p a,b,p,a \perp p a,b,p,a⊥p ,求满...
2021-11-06
0
277
[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
狄利克雷卷积
定义: 对于两个数论函数 f ( x ) , g ( x ) f(x),g(x) f(x),g(x) 那么它们的卷积 h ( x ) h(x) h(x) 记作 f ( x ) ∗ g ( x ) f(x) * g(x) f(x)∗g(x),式子如下: f ( x ) ∗ g ( x ) ...
2021-11-06
0
501
[洛谷 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
杜教筛
杜教筛 杜教筛可以在 O ( n 2 3 ) O(n ^{\frac{2}{3}}) O(n32) 的复杂度内求解积性函数的前缀和 设数论函数 f ( x ) f(x) f(x),求 ∑ i = 1 n f ( i ) \sum_{i=1}^{n}f(i) i=1∑nf(i) 令 ...
2021-11-06
0
263
[洛谷 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
首页
上一页
1
2
3
下一页
末页