题解：CF1731E Graph Cost

首先有一个结论，能选大的

k

就尽量选大的。

证明：我们要使花费代价最小，然而添加的边数是固定的，即，我们要让添加的平均代价最小。那么如果选

k

条边，平均每条边的代价为

\dfrac{k+1}{k}

。如果选

k+1

条边，平均每条边的代价为

\dfrac{k+2}{k+1}

，通分得

\dfrac{k^2+2k+1}{k^2+k}>\dfrac{k^2+2k}{k^2+k}

。显然后者代价更小。故得证。

那么我们就从

n

开始枚举

k

，对于每一个枚举到的

k

，我们怎么判断有没有

k+1

对点能满足

\gcd(u,v)=k+1

呢？

最大公约数有一个性质：若

\gcd(u,v)=g

，则

\frac{u}{g}\bot\frac{v}{g}

。证明显然，这里不提。

那么我们判断最大公约数就可以转化为：从

1

到

\frac{n}{k+1}

中有没有

k+1

对数互质。

也就是要解决这样一个问题：求

[1,p]

中的互质数组数。

怎么解决？暴力枚举+根号枚举判断？太慢了，是

O(n^2\sqrt n)

的。

有互质，可以往欧拉函数上面想。根据欧拉函数的定义，有

\phi(n)=\sum\limits_{i=1}^nn\bot i

。就是说，

\phi(n)

为

[1,n]

中，与

n

互质的数的个数。

这个定义很优美。为什么这么说？可以想到，其前缀和

sum=\sum\limits_{i=1}^n\phi(i)

的值不就是

[1,n]

中，互质数的组数吗？

求

[1,n]

欧拉函数及其前缀和的方法是线性筛，其可以做到

O(n)

。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6+10;
int phi[N],sum[N],Prime[N],cnt;
bool vis[N];
void Getphi(){
	phi[1] = 1;
	for(int i = 2;i<N;i++){
		if(!vis[i]){
			vis[i] = i;
			Prime[++cnt] = i;
			phi[i] = i - 1;
		}
		for(int j = 1;j<=cnt;j++){
			if(i*Prime[j] > N) break;
			vis[i*Prime[j]] = Prime[j];
			if(i%Prime[j] == 0){
				phi[i*Prime[j]] = phi[i]*Prime[j];
				break;
			}
			phi[i*Prime[j]] = phi[i]*phi[Prime[j]];
		}
		sum[i] = sum[i-1] + phi[i];
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T; cin>>T;
	Getphi();
	while(T--){
		int n,m,ans = 0;
		cin>>n>>m;
		for(int k = n;k>=1;k--){
			int maxn = min(sum[n/(k+1)],m)/k;
			ans += maxn * (k+1);
			m -= maxn * k;
		}
		cout<<(m > 0 ? -1 : ans)<<'\n';
	}
	return 0;
}

题解：CF1731E Graph Cost

文章操作

相关推荐

评论

题解：CF1731E Graph Cost