题解：P3764 签到题 III

· · 题解

题目大意

定义 f(a,b)=\begin{cases}f(a-b,2b)+1,&a>b\\f(2a,b-a)+1,&a<b\\0,&a=b\,或无解\end{cases}，

求 \displaystyle\sum_{i=1}^n\sum_{j=1}^nf(i,j) 的值。

性质发现（※）

最终结论：

若 (a,b)=1：

“当且仅当 a+b=2^k 时，f(a,b)=k-1（结论 I）；否则 f(a,b)=0（结论 II）。”

否则：

“f(a,b)=f(\frac{a}{(a,b)},\frac{b}{(a,b)})（结论 III）。”

证明：

1\degree

对于 f(a,b) 和 f(b,a)，考虑前者运算过程与后者运算过程除了 f 中两个数字的顺序不同，其他都相同，故最后的结果相同，于是有 f(a,b)=f(b,a)；

2\degree

由定义和 1\degree 的结论，将运算过程简化为

--- ### $3\degree

考虑 a,b 不互质的情况，不妨设 (a,b)=m，发现 f(a,b) 运算过程中的数字是 f(\frac{a}{m},\frac{b}{m}) 运算过程中数字的 m 倍，不影响结果，则有 f(a,b)=f(\frac{a}{m},\frac{b}{m})；至此最终结论 III 证毕。

4\degree

考虑最终结论 I：当 a+b=2^k,(a,b)=1 时，f(a,b)=k-1。

由 1\degree，不妨设 a<b。因为 a+b 是偶数，且 a,b 互质，故 a,b 均为奇数。所以有：

\displaystyle f(a,b)(\textcircled{1})\xlongequal{2\degree}f(2a,b-a)+1\xlongequal{a,b为奇数,且3\degree}f(a,\frac{b-a}{2})+1(\textcircled{2})

考虑第 \textcircled{1} 步中，a+b=2^k，(a,b)=1，第 \textcircled{2} 步中，a+\frac{b-a}{2}=2^{k-1}，(a,\frac{b-a}{2})=1；故形如递归，则第 k-1 步时，a_{k-1}+b_{k-1}=2，进而地，a_{k-1}=b_{k-1}=1，f(a,b)=f(a_{k-1},b_{k-1})+k-1=k-1。

5\degree

考虑最终结论 II：当 a+b\ne2^k,(a,b)=1 时，f(a,b)=0。

类比上述过程，由互质可得两种情况：

设 $a<b$，则 $f(a,b)=f(2a,b-a)$；考虑 $f(2a,b-a)$ 与 $f(a,b)$ 本质相同（一奇一偶）且不能被转化为 $4\degree$，故**不可能终止**。 $(2)\quad a,b$ 均为奇数 设 $a<b$，类比 $4\degree$ 中推导，则 $f(a,b)=f(2a,b-a)=f(a,\frac{b-a}{2})$；此时 $a+\frac{b-a}{2}=\frac{1}{2}(a+b)$，所以每递归一层会使两个数的和除以 $2$。因为 $a+b\ne2^k$，所以可以在有限次递归后变为 $f(a_n,b_n)(a_n,b_n一奇一偶)$，即 $(1)$。 # 做法（※） ## 朴素做法 此时，原式中每一个 $f(i,j)$ 均可快速（**近乎**常数地）解决，但仍然是 $\mathcal O(n^2)$。 ## 优化 1 考虑变成单层求和。对于每个奇数 $i$，找到**唯一**比它小的 $j$ 满足 $i+j=2^{k}$ 且 $(i,j)=1$（对答案有贡献）。即： $\displaystyle\sum_{i=1}^n [i\bmod2=1]\lfloor \log_2(i)\rfloor\lfloor\frac{n}{i}\rfloor

（编者注：这个式子别人都没讲，本人来说一下。对于一组有贡献的 f(a,i)，可以找出 \lfloor\frac{n}{i}\rfloor 组 f(ka,ki) 有同样贡献；考虑单组贡献

而只讨论奇数**显然不会重复/遗漏**，故得证。） 此时发现时间复杂度是 $\mathcal O(n)$ 的。 ## 优化 2 进而地，我们发现形如下列式子可以进行**数论分块**。 $\displaystyle\sum_{i=1}^ng(i)\times\lfloor\frac{n}{i}\rfloor \displaystyle\sum_{i=1}^ng(i)\times\lfloor\log_2(i)\rfloor

那么本题也必然能通过上述两个数论分块来完成优化。数论分块时间复杂度 \mathcal O(\sqrt{n}\log n)。

代码

总之还是有点细节的（主要是我之前没写过分块 orz）。

如果不会同时处理两个分块，可以采用“分块套分块”的形式，在 \sqrt{n} 里套一个 \log n，详见代码。

//Luogu P3764 author: OrientDragon
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
inline int solve(int n){//代码在这里 
    function<int(int,int,int)>f=[](int l,int k,int n){
        function<int(int,int)>od=[](int x,int y){
            //[x,y]中有多少个奇数，选用大模拟O(1)处理
            if((y-x+1)&1&&x&1)return((y-x+1)>>1)+1;
            else return(y-x+1)>>1;
        };
        //log数论分块
        int ret=0,r=0,tmp=0;
        for(;l<=k;l=r+1){//O(log(n))
            tmp=log2(l);
            r=min((1ull<<(tmp+1))-1,k);
            tmp*=n/l;
            ret+=tmp*od(l,r);//核心 
        }
        return ret;
    };
    //一般数论分块模板
    int ans=0,l=1,r=0;
    for(;l<=n;l=r+1){//O(sqrt(n))
        r=n/(n/l);
        ans+=f(l,r,n);//这里是用于处理log的区间和 
    }
    return ans<<1;
}main(){int n;cin>>n;cout<<solve(n);}