数论分块、杜教筛思想、莫比乌斯反演初探
2022/4/10 23:13:09
本文主要是介绍数论分块、杜教筛思想、莫比乌斯反演初探,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1 1.对于L,R; 2 找到最大的R,使得[n/l]=[n/r]; 3 n/r>=[n/r]-->r<=n/[n/r] 4 <<=>> 5 r<=n/[n/l]; 6 7 2. 8 [[n/x]/y]=[n/xy] 9 10 3.杜教筛 11 i >= 1 && i <= n j >= 1 && j <= n 12 求它们的互质对数 13 令f(n)=它们的互质对数; 14 f(n)=n^2-不互质对数 15 即f(n)=n^2-(∑(i,j)=d) d从2->n; 16 对于i,j他们gcd=d,则I,J互质;且I,J<=[n/d]; 17 即等价求I,J,在[n/d]下的互质对数,子问题; 18 所以f(n)=n^2-∑f(n/d) ;复杂度是O(n^3/4); 19 能优化到O(n^2/3); 20 当n<=n^2/3时用线性筛,大于用递归,递归复杂度是o(3/4) 0.75; 21 22 23 24 数论函数:定义域是整数的函数 ; 25 积性函数:(a,b)=1,有f(a,b)=f(a)*f(b); 26 f(n)=f(p1^e1)*...*f(pk^ek); 27 28 29 莫比乌斯函数 30 31 u(n) 当 n有平方因子 u(n)=0,也就是n=pk^ek, ek>=2; 32 当n=1,u(n)=1; 33 当n=p1..pk时,u(n)=(-1)^k; 34 35 迪利克雷卷积(适用于数论函数)有交换律,分配律,结合律; 36 形如h=f*g; //*是卷积符号不是乘法 37 h(n)=∑f(d) x g(n/d),d|n;这是x乘法 ,*这里代表卷积符号; 38 39 若f(n)=1,f*f f卷f 40 f*f=n的因子个数 ∑f(d)xf(n/d) 41 所以h(n)=∑f(d)xf(n/d) 42 43 2.若id(n)=n,f(n)=1, 44 则h(n)=∑1xn/d =因子之和 45 46 f,g是积性函数,则f*g也是积性函数 47 f*g=f(d)xg(n/d)显然如果f,g为积性函数,则能展开 48 49 莫比乌斯反演 50 f(n)=∑g(d),d|n //f=g*1; 51 能推出g(n)=∑f(d) x u(n/d),d|n ; //g=f*u 52 53 证明; 54 f*u=g*1*u; 证明(1*u)=e;其中e, e(n),当n=1时,e(n)=1,n≠1时,e(n)=0; 55 证明1*u=∑u(d) ,d|n ,考虑n=p1^e1..pk^k;有k种因子;则由莫比乌斯u函数知道,只有1次因子才会被统计 56 即,∑u(d) ∑(-1),(c,k,i)=0 =(1-1)^k;证毕; 57 等价于f*u=g*e=g; 58 即g(n)=f*u证毕;
这篇关于数论分块、杜教筛思想、莫比乌斯反演初探的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?