【枚举gcd】P4571 [JSOI2009] 瓶子和燃料

Love The Way You Lie 2024-03-22 16:31 111阅读 0赞

gcd的经典套路，枚举gcd即可

[P4571 \[JSOI2009\] 瓶子和燃料 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P4571 _JSOI2009_ _ - _ _ _ _luogu.com.cn]

题意：

![347c3fea95c448adaaccaeb16c960b28.png][]

思路：

就是让你在n个值里选k个值，使得其gcd最大

即gcd(b1,b2,....bk)最大

设gcd(b1,b2,....,bk)=t

枚举t即可

然后合法性就是看t的出现次数是否>=k

统计最大的t即可

Code:

#include <bits/stdc++.h>
    
    #define int long long
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=3e5+10;
    const int mod=1e9+7;
    
    map<int,int> mp;
    
    int N,K;
    int a[mxn];
    
    void solve(){
    	cin>>N>>K;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N;i++){
    		int u=a[i];
    		set<int> S;
    		for(int j=1;j<=u/j;j++){
    			if(u%j==0){
    				S.insert(j);
    				if(j!=u/j) S.insert(u/j);
    			}
    		}
    		for(auto it:S) mp[it]++;
    	}
    	int ans=0;
    	for(auto it:mp){
    		if(it.second>=K) ans=max(ans,it.first); 
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[P4571 _JSOI2009_ _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P4571
[347c3fea95c448adaaccaeb16c960b28.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/783f5ed7fe8e4aeba32ed8dd0119dfe0.png

发表评论取消回复

表情：

评论列表（有 0 条评论，111人围观）

还没有评论，来说两句吧...

相关阅读

相关如何枚举一个枚举

问题描述：如何在 C\ 中枚举 enum？例如，以下代码无法编译： public enum Suit { Spa

今天药忘吃喽~/ 2024年03月31日 17:45/ 0 赞/ 192 阅读

相关【枚举gcd】P4571 [JSOI2009] 瓶子和燃料

gcd的经典套路，枚举gcd即可 [P4571 \[JSOI2009\] 瓶子和燃料 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P4571 _JSO

Love The Way You Lie/ 2024年03月22日 16:31/ 0 赞/ 112 阅读

相关枚举和注解。

推荐使用枚举定义常量 1、枚举常量更简单 2、枚举常量属于稳态型 3、枚举具有内置方法 4、枚举可以自定义方法枚举类型是不能有继承的，也就是说一个枚举常量定义

r囧r小猫/ 2024年02月18日 20:41/ 0 赞/ 117 阅读

相关 c#枚举数字转枚举_C＃中的枚举（枚举）

c\枚举数字转枚举 enum stands for enumeration, it is a set of named integer constants, their de

深藏阁楼爱情的钟/ 2023年03月05日 11:58/ 0 赞/ 64 阅读

相关 c++枚举和c语言枚举_C语言枚举初学者指南

c++枚举和c语言枚举 Hey, folks! Hope you all are doing well. In this article, we will be discus

曾经终败给现在/ 2023年02月28日 06:05/ 0 赞/ 314 阅读

相关【枚举】信息类枚举

> `前言` 比如用户信息里面有个等级，12345。通常，我们是建一个枚举类。替代方法：在实体类下添加自定义获取名称的方法。好处：如果项目服务很多，方

拼搏现实的明天。/ 2022年12月24日 01:54/ 0 赞/ 353 阅读

相关枚举

JDK1.5之前需要自定义枚举类 JDK 1.5 新增的 enum 关键字用于定义枚举类若枚举只有一个成员, 则可以作为一种单例模式的实现方式枚举类对象的属性

亦凉/ 2022年03月22日 02:54/ 0 赞/ 385 阅读

相关枚举

枚举什么是枚举？枚举指的是在一定范围内取值，这个值必须是枚举类型中的任意一个，而且只能够取其中的一个枚举的特点： 1.枚举的本质就是一个Java类

叁歲伎倆/ 2022年03月18日 01:28/ 0 赞/ 452 阅读

相关枚举

枚举（穷举，暴力求解）一.基本思想对问题变量可能解集合的每一个元素，根据问题给出

- 日理万妓/ 2021年12月16日 15:34/ 0 赞/ 424 阅读

相关洛谷 P4571 BZOJ 2257 [JSOI2009]瓶子和燃料

[bzoj题目链接][bzoj] > 上面hint那里是选择第2个瓶子和第3个瓶子 Time limit 10000 ms Memory limit 131072 kB

淡淡的烟草味﹌/ 2021年11月02日 00:20/ 0 赞/ 277 阅读