Java教程

数论分块、杜教筛思想、莫比乌斯反演初探

本文主要是介绍数论分块、杜教筛思想、莫比乌斯反演初探,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
 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证毕; 

 

这篇关于数论分块、杜教筛思想、莫比乌斯反演初探的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!