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证毕；