关于数论分块里r=sum/（sum/l）的证明！

今天的模拟赛里T2要使用到数论分块，里面有一个重要的坎就是关于r=sum/（sum/l）的证明，网上关于这道题的题解里都没有关于这个的证明，那么我就来填补一下：

在以下的文章里，我都会使用lo（x）表示对x向下取整，同理up（x）表示对x向上取整;

我们要求左右区间的边界，那么我们就不妨设取两个数 i 和 i‘ 使得lo（N/i'）==lo（N/i）则，我们就可以证明

设 lo（N/i）=k;则有 k*i+p=N (p一定有 0<=p<i 成立) 　　设i’=i+d 则有 lo（N/i+d）=k;则有 k*(i+d)+p'=N;

所以： p'=N-k*i-k*d ;

因为 p=N-k*i;

so p'=p-k*d;

because k*d=N-k*i-p'=p-p' also because 0<=p<=i

so k*d+p'=p -> d(max)=lo(p/k);　　　　　　　　(this can make each other !)

because i'=i+d(max)=i+lo(p/k)=i+lo((N%i)/(N/i));

-> i+lo((N-lo(N/i)*i)/lo(N/i));

->lo(i+lo((N-lo(N/i)*i)/lo(N/i)));

->lo((lo(N/i)*i)/lo(N/i)+((N-lo(N/i)*i)/lo(N/i)));

->lo(N/lo(N/i));

证明完毕！！（学校输入法真的难使，我也不想打英文的！）

更加帅气的证明：

设floor(x)表示小于等于x的最大整数，那么若有 floor(N/i)=floor(N/i') ,则i'的最大值为floor(N/floor(N/i));
证明：
我们设 floor(N/i)=k ,显然一定有整数p∈[0,i)满足 k*i+p=N ;
则 p=N-k*i ;
设 d=i-i';
若有整数p'满足 k=floor(N/(i+d)),N=k*(i+d)+p',
那么p'=(N-k*i)-k*d=p-k*d,即 k*d=p'-p;
又∵ p∈[0,i) ∴当d取得最大值dmax时 k*dmax+p'=p，dmax=floor(p/k);
i'=i+dmax
=i+floor(p/k)
=i+floor((N%i)/(N/i))
=i+floor((N-floor(N/i)*i)/floor(N/i))
=floor(i+floor((N-lo(N/i)*i)/floor(N/i)))
=floor((floor(N/i)*i)/floor(N/i)+((N-floor(N/i)*i)/floor(N/i)))
=floor(N/floor(N/i))
即 i'=floor(N/floor(N/i));
得证。

巴特西

关于数论分块里r=sum/（sum/l）的证明！

最新文章

热门文章