Answer :本题突破口在于
gcd(a,b)=gcd(a,a+b)
然后将右部点选择性合并后 直接求gcd(c1-ck)即可
坑点:遍历mp的时候注意 略过空集
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e6+5;
map<vector<int>,LL>mp;
map<vector<int>,LL>::iterator it;
vector<int>G[maxn];
int n,m;
LL c[maxn];
int main(){
int _;scanf("%d",&_);
while(_--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&c[i]);
}
for(int i=1,u,v;i<=m;i++){
scanf("%d %d",&u,&v);
G[v].push_back(u);
}
for(int i=1;i<=n;i++){
sort(G[i].begin(),G[i].end());
if(G[i].size())
mp[G[i]]+=c[i];
}
LL ans=0;
for(it = mp.begin();it != mp.end();it ++){
ans=__gcd(ans,it->second);
//cout<<it->second<<'\n';
}
printf("%lld\n",ans);
mp.clear();
for(int i=1;i<=n;i++) G[i].clear();
}
}