首页 > 其他 > 详细

洛谷P1414 又是毕业季II

时间:2020-02-17 21:49:27      阅读:61      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 

 

k个数的公约数的含义是这k个数中均含有某个因数, 因此我们只需把所有数的因数求出来,发现有k个数均含有某个因数,那么这个数必然是这k个数的公约数

因此此题的思路就是求出每个数的因子,并存储每个因子出现的次数。最后搜索这个数组就行 题目还保证了单调性

技术分享图片
#include<iostream>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<queue>
#include<stack>
#include<list>
#include<sstream>
#include<cstdio>
#define INF 0x3f3f3f3f
const int maxn = 1e6 + 5;
const double PI = acos(-1.0);
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
int c[maxn];
int Max;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        Max = max(Max, x);
        int m = sqrt(x);
        for (int i = 1; i <= m; i++) {
            if (x % i) {
                c[i]++;
                if (x != i * i) c[x / i]++;
            }
        }
    }
    int x = Max;
    for (int i = 1; i <= n; i++) {
        while (c[x] < i) x--;
        printf("%d\n", x);
    }
    return 0;
}
View Code

 

洛谷P1414 又是毕业季II

原文:https://www.cnblogs.com/hznumqf/p/12323513.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!