网站建设类别,网页设计基础教程,网站建设的比较合理的流程,商城建设开发解析
神仙题了属于是 设SiS_iSi为右侧第i个点连向的左侧点的集合 然后把所有SiS_iSi 相同的点合并成一个点#xff08;就称为新点吧#xff09;#xff0c;点权相加 合并后的所有点权的gcd#xff08;设为w吧#xff09;就是答案
为什么#xff1f; 首先一个显然的…解析
神仙题了属于是 设SiS_iSi为右侧第i个点连向的左侧点的集合 然后把所有SiS_iSi 相同的点合并成一个点就称为新点吧点权相加 合并后的所有点权的gcd设为w吧就是答案
为什么 首先一个显然的结论是SiS_iSi相同的点要么都被选到要么都选不到 然后考虑任何一个左侧点的选取方案权值肯定是一些新点的权值和 因此w也一定是这个方案权值的因子 w的合法性得以证明
然后是w的最优性 考虑假设有一个x是比w更大的符合的答案 那么一定至少存在一个新点k使x不是它的因子了 那么考虑当选取的集合为SkS_kSk的时候都权值和 如果这个权值和仍是x的倍数说明至少存在一个新点k′kk′使Sk′S_{k}Sk′是SkS_{k}Sk的子集且k’的权值也不是x的倍数这样他们加起来才可能是x的倍数 那么把k’作为新的k递归到考虑选取集合为Sk′S_{k}Sk′的情况 这样集合会越来越小直到无法找出新的k’为止就一定能找到一种方案使x不是该方案权值的因子 最优性得以证明
思路有了以后代码实现就不难了 我偷懒没有用哈希使用的是map套vector
#includebits/stdc.h
using namespace std;
#define ll long long
const int N5e5100;
ll read() {ll x0,f1;char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {xx*10(c^48);cgetchar();}return x*f;
}int n,m;
#define V vectorint
V v[N];
mapV,llmp;
mapV,ll::iterator it;
ll gcd (ll a,ll b){return b?gcd(b,a%b):a;
}
ll a[N];
int main() {
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifint Tread();while(T--){mp.clear();ll ans0;nread();mread();for(int i1;in;i){v[i].clear();v[i].shrink_to_fit();}for(int i1;in;i) a[i]read();for(int i1;im;i){int xread(),yread();v[y].push_back(x);}for(int i1;in;i){if(v[i].size()0) continue;sort(v[i].begin(),v[i].end());mp[v[i]]mp[v[i]]a[i];}for(itmp.begin();it!mp.end();it){ll o(*it).second;//printf(o%lld\n,o);ansgcd(o,ans);}printf(%lld\n,ans);}return 0;
}
/*
3
501 502 503
*/
