注意本文有些时候对[]的定义不太准确&#xff0c;有时候指的是向下取整&#xff0c;有时候指的是判断符号&#xff0c;当然看一看里面有没有<,>,<&#61;,>&#61;...就可以区分&#xff0c;不太严谨&#xff0c;望周知。
现在我们要解决这样一个问题&#xff1a;
我们考虑当的时候&#xff0c;应该怎么做。
很明显直接把它拆开来&#xff1a;
那么我们就得到了一条式子。
如果不是呢
我们可以发现&#xff0c;这个式子在干什么&#xff1f;
其实是在数这条直线下方&#xff0c;而且y>0的整数点。整数点指的是(x,y)&#xff0c;x&#xff0c;y都为整数。
当然x的取值范围肯定是&#xff0c;我们设这个函数在的最大值为。
那么上面的式子就可以写成&#xff1a;
我们乱搞一下&#xff1a;
这四条式子都十分地显然。
我们考率一下&#xff0c;后面那一个东西怎么样可以很快地算出后面那个求和。
明显相当于我们看一下上面的整数点有多少,那就相当于。
所以
所以
复杂度好像很难看出来。
其实只看a,c两位&#xff0c;当a为0的时候&#xff0c;就可以直接算出来了。
常数是欧几里得算法的2倍。
c是不可能为0的&#xff0c;可以自己想一想。