Reverse Card (Hard Version)

标签：le frac Reverse sum Hard mid mu Version gcd

事情是这样的，我验了这一场 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 | gc
		for (auto u : fac[gc]){
			if (u==gc){
				continue;
			}
			int s=n/gc;
			// 1<=pa,pb<=s
			// gcd(pa,pb)=1
			int l=gc/u;
			// pa+pb=l
			s=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;
}

哦这只能说明我数学不好。为了防止大家被魔怔，我贴一个出题人发我的正解。

其实有一定的相同，就是后面的枚举不同。

标签：le,frac,Reverse,sum,Hard,mid,mu,Version,gcd
From： https://www.cnblogs.com/SFlyer/p/18169126