题解 P3764 【签到题 III】

· · 题解

听说没人证出、、其实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.