AtCoder Beginner Contest 191 F - GCD or MIN

链接

题意:

给定一个数组,每次从数组中拿两个数A 、B出来,再放一个数C进去,且C = min(A , B) 或者 C = gcd(A , B),问剩下的最后一个数有多少种可能。

思路:

假设数组为 a[ ]

首先,如果对所有的数取min的话,那么留下来的一定是最小的那个。

其次,对于一个式子 C = GCD(A , B) , 那么一定满足:C <= A && C <= B

于是,无论剩下的最后一个数是多少 (假设他是ans),一定有 ans <= min(a[1],a[2]...a[n]) 

条件①:ans <= min(a[1],a[2]...a[n]) 

接着我们可以发现,ans 一定是 a[i]的因子,因为gcd(A,B)本身就是在寻找A、B中最大相同因子

条件②:ans 是a[i]的因子

所以我们就对a[i]的因子进行筛选,什么样的因子可以作为答案?

样例1:

AtCoder Beginner Contest 191  F - GCD or MIN

 

可以发现 1 这个因子,其实是三个数*有的因子,为什么它不作为答案的一部分?(答案是3和6)

换句话说,1这个因子太小了,小到无论用min或者gcd,都到达不了它,那我们就筛出可以到达的因子。

换句话说,对于一个因子T ,假如有一部分的数,可以通过gcd或者min的操作得到因子T,那么这个因子T就对答案的贡献+1。

并且,gcd其实比min更容易得到更小的数(这个好理解)

所以对于一个因子T,把所有包含这个因子的a[i]集合进行GCD操作,即如果a[1],a[2],a[3]为数组中所有包含因子T的数,那么我取minn = gcd(a[1],a[2],a[3])

此时的minn是我能通过gcd(与min操作)这些数的最小的数了,如果minn <= T (其实这里我没有太想好应该写等号还是小于等于,因为minn=gcd(所有包含因子T的数),思考有没有可能minn小于T,但是gcd(部分包含因子T的数) = T ) , 那么cnt ++

 

于是我写的是:

  先找出a[i]的所有小于min(a[1],a[2]...a[n]) 因子,然后判断所有包含这个因子的数的gcd是否小于这个因子,是就++

参考此处

代码:

AtCoder Beginner Contest 191  F - GCD or MIN
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pb push_back
#define debug(a) cout << #a << ' ' << a << '\n';
#define debug2(a , b) cout << #a << ' ' << a << " || " << #b << ' ' << b << '\n';
#define ye cout << "YES\n";
#define no cout << "NO\n";
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
using namespace std;
int a[maxn];
map<int , int>ma;
int cnt = 0; 
int re[maxn];
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n ;
    cin >> n;
    int minn = 1e18;
    for(int i = 1 ; i <= n ; i ++) cin >> a[i] , minn = min(minn , a[i]);
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j * j <= a[i] ; j ++){
            if(a[i] % j == 0){
                if(ma[j] == 0){
                    ma[j] = ++ cnt;
                }
                re[ma[j]] = __gcd(re[ma[j]] , a[i]);
                if(a[i] / j != j){
                    int now = a[i] / j;
                    if(ma[now] == 0){
                        ma[now] = ++ cnt;
                    }
                    re[ma[now]] = __gcd(re[ma[now]] , a[i]);
                }
            } 
        }
    }
    int ans = 0;
    for(auto i : ma){
        if(re[i.second] <= minn && re[i.second] <= i.first){
            ans ++;
        //    debug2(i.first , re[i.second])
        } 
    }
    cout << ans << '\n';
    return 0;
}

/*
6
2 2 1 3 2 2
*/
View Code

 

上一篇:ybtoj·最大均值【二分】


下一篇:洛谷P5278 算术天才⑨与等差数列