事情是这样的，我验了这一场 CF。显然我玩原神玩多了有一个很奇怪的、不能过的算法，哦，当然，在我本机可以过。为了展现自己的智慧糖，我写一下。
出题人是先发给我了一个限制都是 \(n\) 的，因此只有这个。\(n,m\) 改改就是了。
要求 \(1\le a\le n,1\le b\le n\) 满足
- \(a+b\mid b\times \gcd(a,b)\) 的个数。
\[a+b\mid b\times \gcd(a,b)\Leftrightarrow \frac{a+b}{\gcd(a,b)}\mid b
\]
设 \(a=p_ag,b=p_bg\)，其中 \(g=\gcd(a,b)\)。则
\[\Leftrightarrow p_a+p_b\mid gp_b
\]
则
\[k(p_a+p_b)=gp_b\implies kp_a=(g-k)p_b
\]
因为 \(p_a,p_b\) 互质，则 \(k=\alpha p_b,g-k=\alpha p_a\)，则 \(g=\alpha(p_a+p_b)\)。
则
\[\Leftrightarrow p_a+p_b\mid g \Leftrightarrow \frac{a+b}{\gcd(a,b)}\mid \gcd(a,b)
\]
所以可以枚举 \(\gcd(a,b)=g\)，我们就要求 \(p_a,p_b\in \mathbb{N}^+\) 满足
- \(p_a+p_b-\lfloor \frac{n}{\gcd(a,b)}\rfloor \le p_a,pb\le \lfloor \frac{n}{\gcd(a,b)}\rfloor\)。
- \(\gcd(p_a,p_b)=1\)。
我们枚举 \(p_a+p_b\) 的值是什么，\(\mathcal{O}(n\ln n)\)。则我们要求：
设 \(l=p_a+p_b,s=l-\lfloor \frac{n}{\gcd(a,b)}\rfloor,t=\min(\frac{n}{\gcd(a,b)},l-1)\)。
\[\begin{aligned}
&\sum_{p_a=s,p_b=l-p_1}^{p_a\sim t} [\gcd(p_a,p_b)=1] \\
=& \ \sum_{p_a=s}^t \sum_{d\mid \gcd(p_a,l-p_a)}\mu(d) \\
=& \ \sum_{d} \mu(d) \sum_{p_a=s}^t [d\mid p_a][d\mid l-p_a] \\
=& \ \sum_{d} \mu(d) \sum_{p_a=s}^t [d\mid p_a][d\mid l]\\
=& \ \sum_{d\mid l} \mu(d) \sum_{p_a=s}^t [d\mid p_a] \\
=& \ \sum_{d\mid l} \mu(d) (\lfloor \frac{t}{d} \rfloor-\lfloor \frac{s-1}{d} \rfloor) \\
\end{aligned}
\]
这个我们枚举 \(d\) 就可以了。时间复杂度 \(\mathcal{O}(n\ln\ln n)\)。
鉴定为最近学莫比乌斯函数被魔怔了。以下是 \(n,n\) 的 code：
#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 1e6+6;ll pr[N],cnt,mu[N],vis[N];
vector<int> fac[N];
void init(){mu[1]=1;for (int i=1; i<N; i++){for (int j=i; j<N; j+=i){fac[j].push_back(i);}}for (int i=2; i<N; i++){if (!vis[i]){mu[i]=-1;pr[++cnt]=i;}for (int j=1; j<=cnt && i*pr[j]<N; j++){vis[i*pr[j]]=1;if (i%pr[j]==0){break;}else{mu[i*pr[j]]=-mu[i];}}}
}ll n,p;int main(){ios::sync_with_stdio(false);cin.tie(0);init();cin>>n>>p;ll ans=0;for (int gc=1; gc<=n; gc++){// (a+b)/gc | gcfor (auto u : fac[gc]){if (u==gc){continue;}int s=n/gc;// 1<=pa,pb<=s// gcd(pa,pb)=1int l=gc/u;// pa+pb=ls=min(s,l-1);int ss=l-s;if (s*2<l){continue;}for (auto v : fac[l]){ans+=mu[v]*((ll)(s/v)-(ll)((ss-1)/v));}}}cout<<ans%p<<"\n";return 0;
}
哦这只能说明我数学不好。为了防止大家被魔怔，我贴一个出题人发我的正解。
其实有一定的相同，就是后面的枚举不同。
