HackerRank The Chosen One [预处理][gcd]

测试账号 2021-01-12 03:25 489阅读 0赞

题解：  
tags:\[预处理\]\[gcd\]  
故事背景：光头钻进了茫茫人海。  
这是一个典型の通过前缀后缀和来降低复杂度的问题。  
先用pre数组与suf数组分别维护前缀gcd和后缀gcd。  
如果 a\[i\] % gcd(pre\[i-1\], suf\[i+1\]) != 0;  
那么光头就从人群中钻出来了！  
gcd(pre\[i-1\],suf\[i+1\])就是我们要的答案。  
注意n=1时的特判！

code：

#include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long LL;
    const int NICO = 100000 + 10;
    int n; vector<int> v;
    LL a[NICO], pre[NICO], suf[NICO];
    LL gcd(LL x, LL y)
    {
        return (y==0)?x:gcd(y, x%y);
    }
    int main()
    {
        scanf("%d", &n);
        for(int i=1;i<=n;i++)
        {
            cin >> a[i];
        }
        if(n == 1)
        {
            cout << (LL)2e18 << endl;
        } else {
            int pos = 0;
            pre[1] = a[1]; suf[n] = a[n];
            for(int i=2;i<=n;i++)
            {
                pre[i] = gcd(a[i], pre[i-1]);
            }
            for(int i=n-1;i>=1;i--)
            {
                suf[i] = gcd(a[i], suf[i+1]);
            }
            for(int i=2;i<=n-1;i++)
            {
                LL tmp = gcd(pre[i-1],suf[i+1]);
                if(a[i] % tmp)
                {
                    pos = i;
                }
            }
            if(a[1] % suf[2])   pos = 1;
            if(a[n] % pre[n-1]) pos = n;
            // pos 表示光头出现的位置
            if(pos==1) swap(a[1], a[2]), pos = 2;
            LL res = a[1];
            for(int i=2;i<=n;i++)
            {   
                if(i!=pos) res = gcd(res, a[i]); // 碰见光头就跳过！
            }
            cout << res << endl;
        }
    }