[题解] AT_abc230_g [ABC230G] GCD Permutation

大家好，我不会莫反，我是暴力老哥。

考虑给定序列

a

求

\gcd(a_i,a_j)\ne 1

的

(i,j)

数量，这是容易做的。我们先对于每个值统计出

\gcd(a_i,a_j)

是其倍数的数量，然后枚举倍数容斥一下即可。

我们考虑本题就相当于做两次上面的东西套起来：先枚举一个值

x

，并计算

x|\gcd(i,j)

的数量，然后容斥。计算这个就是将每个满足

x|i

的

p_i

提出来做上面的东西。

但是直接做跑得很慢。考虑对每个

x

计算的过程。我们先用一个数组

d

记录所有

x|i

的

p_i

的因数

y

并统计每个因数出现次数，之后将

d

排序，从大到小计算对数，然后枚举

y

的倍数并减去倍数的方案数。

我们发现枚举倍数的这部分有两种方法：直接枚举

y

的倍数，或者枚举在

d

中比

y

索引大的位置，并选取其中的倍数。当然两种都无法直接通过。但两者各有优劣，第一种对于较大的

y

运算量很小，而

y

较小时很慢，但第二种中可取的范围总是比较有限。所以考虑每次枚举倍数时选择两种中运算量小的一种。

不会算复杂度，但是没怎么卡常就过了，时间

3.9\text s

。第二种方法中取模比较慢，调一下参可能更快。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) (int)(x).size()
using namespace std;
const int N=2e5+5;
int n,a[N],d[N];
ll f[N],g[N],ans;
basic_string<int> ve[N];
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++)
		for(int j=i;j<=n;j+=i)
			ve[j].pb(i);
	for(int i=2;i<=n;i++){
		int t=0;
		for(int j=i;j<=n;j+=i)
			for(int v:ve[a[j]])
				if(!g[v]++)d[++t]=v;
		sort(d+1,d+t+1);
		for(int j=t;j;j--){
			g[d[j]]=g[d[j]]*(g[d[j]]+1)/2;
			if(n/d[j]<t-j)
				for(int k=d[j]*2;k<=n;k+=d[j])
					g[d[j]]-=g[k];
			else for(int k=j+1;k<=t;k++)
				if(d[k]/d[j]*d[j]==d[k])g[d[j]]-=g[d[k]];
			f[i]+=g[d[j]];
		}
		for(int j=1;j<=t;j++)g[d[j]]=0;
	}
	for(int i=n;i>1;i--){
		for(int j=i*2;j<=n;j+=i)
			f[i]-=f[j];
		ans+=f[i];
	}
	cout<<ans<<'\n';
	return 0;
}

（逃

[题解] AT_abc230_g [ABC230G] GCD Permutation

文章操作

代码

相关推荐

评论

[题解] AT_abc230_g [ABC230G] GCD Permutation