[luogu4571 JSOI2009] 瓶子和燃料 (数论)
2024-09-06 12:52:30
Solution
题目说的很迷,但可以发现两个瓶子互相倒最少是容积的gcd
那么题目就转化为求其中选k个瓶子gcd的最大值,这个可以分解因数,枚举因数得到
Code
//By Menteur_Hxy
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Re register
#define Fo(i,a,b) for(Re int i=(a),_=(b);i<=_;i++)
#define Ro(i,a,b) for(Re int i=(b),_=(a);i>=_;i--)
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin)),p1==p2?EOF:*p1++)
using namespace std;
typedef long long LL;
char buf[1<<21],*p1,*p2;
inline int read() {
int x=0,f=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}
while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int MAXN=1010,MAX=1e7;
int n,k,tot,ans;
int vis[MAX],a[MAX];
map<int,int> id;
int main() {
n=read(),k=read();
Fo(i,1,n) {
int x=read(),sqr=sqrt(x);
Fo(i,1,sqr) if(x%i==0) {
if(!id[i]) id[i]=++tot,a[tot]=i;vis[id[i]]++;
if(!id[x/i]) id[x/i]=++tot,a[tot]=x/i;vis[id[x/i]]++;
}
}
Fo(i,1,tot) if(vis[i]>=k) ans=max(ans,a[i]);
printf("%d",ans);
return 0;
}
最新文章
- AppBox升级进行时 - 扁平化的权限设计
- 实现携程X分钟前有人预定功能
- 转:Git 求生手册 - 第三章分支工作
- Codeforces Round #292 (Div. 2) C. Drazil and Factorial
- H5课程大纲
- [BS-23] AFN网络请求上拉/下拉刷新的细节问题总结
- Android控件之EditText(输入文本框控件)
- SparkSQL相关语句总结
- Windows2003计划任务设置操作手册
- [C++]cin读取回车键
- char 与 unsigned char的本质区别
- python元类理解2
- 【Java】【10】后台处理Emoji表情
- 用好lua+unity,让性能飞起来——lua与c#交互篇
- 70个注意的Python小Notes
- CAS Ticket票据:TGT、ST、PGT、PT、PGTIOU
- Play framework 安装
- Controllerizing the ScrollViewer Thumbnail
- 工控机安装Ubuntu14.04
- bat 调用exe