藿香正气液

【题意简述】

求满足 $1\le x<y\le n$ 且 $\gcd(x,y)=y-x$ 的整数对数量。

【Hint】

令 $d=y-x$。条件变为 $\gcd(x,x+d)=d$，也就是 $d\mid x$。

【提示】

由于 $\gcd(x,x+d)=\gcd(x,d)$，要让它等于 $d$，等价于 $d\mid x$。

【解法】

令 $x=ad$，则 $y=(a+1)d$。只需要满足 $(a+1)d\le n$，即

于是固定 $d$ 的贡献为 $\left\lfloor\dfrac{n}{d}\right\rfloor-1$，并且 $d\le \left\lfloor\dfrac{n}{2}\right\rfloor$。答案为

使用整除分块计算即可。

【推导】

数据点较小时可以直接枚举 $(x,y)$ 并判断条件。令 $d=y-x$ 后，

所以条件等价于 $d\mid x$。写作 $x=td$ 后，$y=(t+1)d$，每个满足 $(t+1)d\le n$ 的正整数对 $(t,d)$ 都对应唯一合法数对，反之亦然；求和没有重复也没有遗漏。

【复杂度】

令 $q=\left\lfloor n/d\right\rfloor$，同一个 $q$ 对应的 $d$ 是一段连续区间，因此可以整除分块。时间复杂度为 $\mathcal{O}(\sqrt n)$，空间复杂度为 $\mathcal{O}(1)$；计数与乘法使用 long long。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/214Name:elixir.cpp5You steal,I kill.6*/7#include <cstdio>8#include <algorithm>9using namespace std;10long long n,Ans;11int main(){12    freopen("elixir.in","r",stdin);13    freopen("elixir.out","w",stdout);14    scanf("%lld",&n);15    long long Limit=n/2;16    for(long long Left=1,Right;Left<=Limit;Left=Right+1){17        long long Value=n/Left;18        Right=min(Limit,n/Value);19        Ans+=(Value-1)*(Right-Left+1);20    }21    printf("%lld\n",Ans);22    return 0;23}