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