首页 > 其他分享 >洛谷题单指南-数学基础问题-P1414 又是毕业季II

洛谷题单指南-数学基础问题-P1414 又是毕业季II

时间:2024-04-15 16:13:35浏览次数:28  
标签:cnt int 洛谷题 个数 P1414 II 因数 INF

原题链接:https://www.luogu.com.cn/problem/P1414

题意解读:有n个数,从其中选k个数,k=1, 2, 3......n,使得这k个数的gcd最大。

解题思路:

如何求k个数的最大公约数呢?暴力法肯定不行。

可以从1到n枚举这个最大公约数i,看是否有>=k个数的因数是i

具体来说,用桶数组存放所有整数,a[x]表示x的个数

对于一个i,对其乘以1,2,3...,只要结果在a中存在,则累加个数到cnt

记录有多少个整数的因数是i,b[cnt] = i

那么要统计k个数的最大公约数的最大值,就统计个数>=k的因数的最大值,max(b[k],b[k+1]......)

举例:

如果b[k] = 10, b[k+1] = 20

显然k + 1个数的因数一定也是k个数的因数,k个数的因数最大值应该是20

只需要逆向处理一遍b,用后一个数和前一个数的因数比较,用较大的更新前一个数的因数:

for(int k = n - 1; k>= 1; i--)  b[k] = max(b[k], b[k + 1]);

再输出b[k]对应结果即可,k=1...n

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 10005, INF = 1000001;

int n, x;
int a[INF], b[N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x, a[x]++;
    for(int i = 1; i < INF; i++)
    {
        int cnt = 0;
        for(int j = i; j < INF; j += i)
        {
            if(a[j]) cnt += a[j];
        }
        b[cnt] = i;
    }
    
    for(int k = n; k >= 1; k--) b[k] = max(b[k], b[k + 1]);
    for(int k = 1; k <= n; k++) cout << b[k] << endl;

    return 0;
}

 

标签:cnt,int,洛谷题,个数,P1414,II,因数,INF
From: https://www.cnblogs.com/jcwy/p/18136168

相关文章

  • 洛谷题单指南-数学基础问题-P1572 计算分数
    原题链接:https://www.luogu.com.cn/problem/P1572题意解读:计算分数+、-运算的结果。解题思路:根据题目要求,逐项计算并约分,则不会超int,问题就比较直接了定义a1/b1为前一项的分子分母,a2/b2为当前项的分子分母依次遍历字符串,处理出分子和分母,本题的关键其实是字符串的处理当读取......
  • 洛谷题单指南-数学基础问题-P4057 [Code+#1] 晨跑
    原题链接:https://www.luogu.com.cn/problem/P4057题意解读:给定三个数,计算其最小公倍数。解题思路:三个数a、b、clcm(a,b,c)=lcm(lcm(a,b),c)100分代码:#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;LLa,b,c;LLgcd(LLa,LLb){i......
  • day01-03_我的Java学习笔记(Java基础语法--注释、字面量、变量、二进制、ASCII编码、
    1.Java基础语法1.1注释1.2字面量(Python中叫数据类型)1.3变量1.3.1变量的定义及使用1.3.2变量使用注意事项1.4数据的存储形式:二进制字节、字、bit、byte的关系:字word字节byte位bit,来自英文bit,音译为“比特”,表示二进制位。字长是指字的......
  • Reflective Journal II
    1.Inthefirstplace,Ithoughtofmygrandpawhenitcometothepersonwhohasagreatinfluenceonme.Therefore,Ichosemygrandpaasthemainroleinmypresentationanddividedfourpointstodescribedetails.AfterfinishingthePPT,Ibegantoge......
  • Reflective Journal II
    1.Firstly,IdecidedwhoIwantedtowriteabout,mymom,consideringtheloveandcomplexrelationshipbetweenus.Then,IfoundasuitablematerialtoputwhatIwantedtoexpressintoit,suchasthephotosofmymomandme,thetopicswetalkedabout,thebea......
  • Reflective Journal II
    Whenitcomestothepeoplewhohaveinfluencedme,IimmediatelythinkofmygoodfriendTang.Firstofall,Ilistedthefoursectionstobeintroduced,thensearchedforphotosoftherelevantcontent,andrecalledthestorybetweenus.Afterfinishing......
  • 代码随想录算法训练营第8天 | 字符串 344.反转字符串 541. 反转字符串II 卡码网:54.
    leetcode344.反转字符串题目344.反转字符串编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用O(1)的额外空间解决这一问题。解题思路实现代码......
  • Reflective Journal II
    Regardingthematerial,consideringmystudentstatus,Ithinkitismoreappropriatetowritemybestfriend.Whenshewasastudent,shehadevenmorecompanionsthanherparents.Ichosevisual,soundandvideoforminsertiontobetterenrichmypresen......
  • Reflective Journal II
    (1)Thefirststepistoidentifythepersontodescribe.Then,Ibegantogatherrelevantimages,audioclipsandothermaterialsthatcouldenhancethemessageandmakepowerpointpresentations.Finally,thinkabouttheconnectivewordsandrecordthev......
  • Reflective journal II
    ReflectivejournalFirstly,Isearchedforasuitablestencilaccordingtomynarrative.Ichosethegreenonebecauseit’sasymbolofenergy,correspondingtomyfriend’scharacters.Infact,Ifeltcomfortableatthesightofthevigorousstencil.Secon......