自动搬运

查看原文

来自洛谷，原作者为

	s_h_y **

搬运于2025-08-24 21:52:27，当前版本为作者最后更新于2017-05-26 22:19:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

听说没人证出、、其实dalao们都是懒得证或者懒得说吧。。

证：当且仅当$i+j=2^{k+1}$且$(i,j)=1$时，$f(i,j)=k$；其余情况$f(i,j)=0$。

一些引理：

$f(\lambda a,\lambda b)=f(a,b)\ \ \ \ (\lambda>0)$

$f(a,b)=f(b,a)$

必要性证明：当$i+j=2^{k+1}$且$(i,j)=1$时，$f(i,j)=k$。

不妨设$i>j$，因为$i,j$互质则有$i,j$都是奇数。

$f(i,j)=f(i-j,2j)+1=f(\frac{i-j}{2},j)+1$

因为$(i,j)=1$，所以$(i-j,j)=1=(\frac{i-j}{2},j)$。

这是一个递归的过程，不同的是，$i+j=2^{k+1}，\frac{i-j}{2}+j=2^{k}$。

故终止时为$f(a,b)|a+b=2^{1}=2$，即$f(i,j)=f(1,1)+k=k$。

充分性证明：当$i+j≠2^{k}$且$(i,j)=1$时，$f(i,j)=0$。

$(1)i+j=s≡1(mod\ 2)$

因为$(i,j)=1$则$i,j$一奇一偶，

若$i>j,f(i,j)=f(i-j,2j);$

若$i<j,f(i,j)=f(2i,j-i);$

因为$(i-j,2j)$或$(2i,j-i)$仍然满足一奇一偶$(≠)$且和为$\frac{s}{gcd(i-j,2j)}$或$\frac{s}{gcd(2i,j-i)}($不可能为$2^{k})$，则其永远无法到达终止状态。

故$f(i,j)=0$。

$(2)i+j=2^{t}·s≡0(mod\ 2)$

令$i>j$，则有$f(i,j)=f(i-j,2j)=f(\frac{i-j}{2},j)$。

而$\frac{i-j}{2}+j=\frac{i+j}{2}=2^{t-1}·s$,

故其可以在有限步递归内转换为$i+j=s≡1(mod\ 2)$即第$(1)$种情况。

故$f(i,j)=0$。

综上得证。

###证by shyakocat

有了这个，我们容易知道公式

$$Ans=\sum_{i=1,i≡1(mod\ 2)}^{n}\lceil log_{2}(i) \rceil \lfloor \frac{n}{i} \rfloor $$

就是对每个i考虑$1<j<i$且$i+j=2^{k}$且$(i,j)=1$，这样的j显然有且仅有1个。再算上倍数即可。

由于很多i的答案一样，可以合并下，时间复杂度$O(\sqrt[]{N}+log(N))$。

var
 n,i,j,a,b,ans:int64;

function min(const a,b:int64):int64;
begin if a>b then exit(b); exit(a) end;

begin
 read(n);
 i:=1;
 while i<=n do
 begin
  a:=n div i;
  b:=trunc(ln(i)/ln(2)+1e-7);
  j:=min(n div a,int64(1)<<(b+1));
  inc(ans,a*b*((j-i+1+j and 1)>>1));
  i:=j+1
 end;
 write(ans*2)
end.