E - Ring MST（n个数裴蜀定理）

E - Ring MST

有i种操作，第i种操作为选择一个数x，然后在x和(x+a[i])%N之间连边，代价为c[i]，问是否能够让图联通，如果可以最小生成树的边权和是多少。

首先按照克鲁斯卡尔算法，我们肯定是按照边权从小到大连。
考虑前i种操作都操作完后的连通块个数。
若u，v在同一联通块，
则
\(u \equiv v+a_1*k_1+a_2*k_2+...a_i*k_i (\mod N)\)
\(u = v+a_1*k_1+a_2*k_2+...a_i*k_i+N*k_{i+1}\)
设\(d=(a_1,a_2,a_3,....a_k,N)\)
u=v+kd
\(u \equiv v (\mod d)\)
也就是有d个连通块

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=3e5+10;
//const int S=1e5+5;
//const int inf=1ll<<60;
const int inf=1<<30;
const ll mo=1e9+7;
struct node{
	ll a,e;
};
node e[N];
ll n,m,x,y;
ll gcd(ll a,ll b){
	if (!b) return a;
	return gcd(b,a%b);
}
int main()
{
//	freopen("data.in","r",stdin);
	
	scanf("%lld %lld",&n,&m);
	fo(i,1,m) scanf("%lld %lld",&e[i].a,&e[i].e);
	sort(e+1,e+m+1,[](node a,node b){
		return a.e<b.e;
	});
	
	ll dd,d,ans=0;
	
	dd=d=n;
	fo(i,1,m) {
		d=gcd(d,e[i].a);
		ans+=(dd-d)*e[i].e;
		dd=d;
	}
	
	if (d!=1) puts("-1");
	else printf("%lld\n",ans);


	return 0;
}