本文共 1249 字，大约阅读时间需要 4 分钟。
由裴蜀定理我们知道，若干的瓶子如此倾倒最小能凑出的是其\(gcd\)
#include #include #include #include #include #include #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair #define LL long long intusing namespace std;const int maxn = 1005,maxm = 1000005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}int n,K;int p[maxm],pi;void sp(int x){ p[++pi] = x; for (int i = 2; i * i <= x; i++) if (x % i == 0){ p[++pi] = i; if (i * i != x) p[++pi] = x / i; }}int main(){ n = read(); K = read(); REP(i,n) sp(read()); sort(p + 1,p + 1 + pi); int ans = 1,cnt = 0; for (int i = 1; i <= pi; i++){ if (p[i] != p[i - 1]){ if (cnt >= K) ans = max(ans,p[i - 1]); cnt = 1; } else cnt++; } if (cnt >= K) ans = max(ans,p[pi]); printf("%d\n",ans); return 0;}
转载于:https://www.cnblogs.com/Mychael/p/9072296.html