A simple Blog for wyx I've been down the bottle hoping.
2257: [Jsoi2009]瓶子和燃料 数论
发表于: | 分类: Oi | 评论:0 | 阅读:108

手动模拟一下,你会发现这个过程其实就是一个更相减损的过程

然后答案就是找$k$个数字使得他们的最大公约数最大

把所有的数字分解因数然后统计出现次数大于等于$k$的最大的那个

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e7+5;

int fac[N], cnt;

inline void calc(int x) {
    int i;
    for(i=1;i*i<x;++i) if(x%i==0) fac[++cnt] = i, fac[++cnt] = x / i;
    if(i*i==x) fac[++cnt] = i;
}

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main() {
    int n,k;
    cin >> n >> k;
    for(int i=1;i<=n;++i) calc(read());
    sort(fac+1,fac+cnt+1);
    int last = 0;
    int ans = 0;
    for(int i=1;i<=cnt+1;++i) {
        if(fac[i] != fac[i-1]) {
            if(last >= k)
                ans = max(ans,fac[i-1]);
            last = 1;
        }   
        else last ++;
    }
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP