CF1322C Instant Noodles

是个汉子 · 2020-09-25 14:55:58 · 题解

Solution

前置知识

因为 \gcd(a,b)|a,\gcd(a,b)|b,\gcd(a,b)|a+b ，而且 \gcd(a,b,a+b)\leq \min(a,b,a+b)\leq a,b\leq a+b ，可以得到 \gcd(a,b)=\gcd(a,b,a+b) 。

题解

我们设 i,j 为右边两个点， S_i,S_j 为两个点所连接的左边的点的集合

当 S_i∩S_j=\varnothing 时，直接求 \gcd(c_i,c_j) 即可

当 S_i=S_j 时，因为一样，所以可以将 c_i 和 c_j 合并起来

当 S_i∩S_j\not=\varnothing 时，求的肯定是 \gcd(c_i,c_i+c_j) 或 \gcd(c_j,c_i+c_j) 或 \gcd(c_i,c_j,c_i+c_j) 结果都是 \gcd(c_i,c_j) 。

其实和别的题解差不多\^o^/，但是咱没用 hash ，因为不会。（而且是完整的代码 ԅ(¯﹃¯ԅ)

代码

#include<bits/stdc++.h>
#define ll long long

using namespace std;
const int N=5e5+10;
int T,n,m;
ll c[N];
set<int> g[N];//我这里是拿set求的集合
map<set<int>,ll> mp;//拿map做的映射

ll gcd(ll x,ll y){
    return y==0?x:gcd(y,x%y);
}

int main(){
    scanf("%d",&T);
    while(T--){
        mp.clear();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&c[i]);
        for(int i=1;i<=n;i++) g[i].clear();
        while(m--){
            int u,v;
            scanf("%d%d",&u,&v);
            g[v].insert(u);
        }
        for(int i=1;i<=n;i++)
            if(!g[i].empty()) mp[g[i]]+=c[i];
        ll ans=0;
        for(auto &i:mp)
            if(ans) ans=gcd(ans,i.second);
            else ans=i.second;
        printf("%lld\n",ans);
    }
    return 0;
}