洛谷P1372 又是毕业季I

迈不过友情╰ 2022-05-26 13:15 172阅读 0赞

## 题目背景 ##

“叮铃铃铃”，随着高考最后一科结考铃声的敲响，三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍，憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑和泪水，全凝聚在毕业晚会上，相信，这一定是一生最难忘的时刻！

## 题目描述 ##

为了把毕业晚会办得更好，老师想要挑出默契程度最大的k个人参与毕业晚会彩排。可是如何挑呢？老师列出全班同学的号数1，2，……，n，并且相信k个人的默契程度便是他们的最大公约数（这不是迷信哦~）。这可难为了他，请你帮帮忙吧！

PS：一个数的最大公约数即本身。

## 输入输出格式 ##

输入格式：

两个空格分开的正整数n和k。（n>=k>=1）

输出格式：

一个整数，为最大的默契值。

## 输入输出样例 ##

输入样例\#1： 复制

4 2

输出样例\#1： 复制

2

##     ##

##     ##

## 说明 ##

【题目来源】

lzn原创

【数据范围】

对于20%的数据，k<=2,n<=1000

对于另30%的数据，k<=10,n<=100

对于100%的数据，k<=1e9,n<=1e9（神犇学校，人数众多）

比如n=4，k=2

1 2 3 4 取2号同学和4号同学最大公约数就是2

再比如n=6，k=2

1 2 3 4 5 6 取3号同学和6号同学就是最大公约数就是3

证明：

首先，若可能的最大公约数为a，取出的k个数为X1，X2，……，Xk且满足X1<X2<……<Xk，那么有X1>=a，X2>=2a，……，Xk>=ka。又∵Xk<=n，∴n>=ka，∴a<=n/k，又∵a为整数，∴a<=\[n/k\]（\[\]为取整符号）。

另一方面，我们取\[n/k\]，2\*\[n/k\]，……，k\*\[n/k\]，它们的最大公约数a=\[n/k\]，且它们都小于等于n大于等于1，且互不相等，满足条件。

∴答案即为\[n/k\]。

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	long long a, b;
    	cin >> a >> b;
    	cout << a / b;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关洛谷——P1838 三子棋I

P1838 三子棋I 题目描述小a和uim喜欢互相切磋三子棋。三子棋大家都玩过是吗？就是在九宫格里面OOXX（别想歪了），谁连成3个就赢了。由于小a比较愚蠢，

青旅半醒/ 2023年10月02日 12:06/ 0 赞/ 12 阅读

相关 P1414-又是毕业季II

1 include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll;

ゝ一纸荒年。/ 2023年06月01日 08:53/ 0 赞/ 11 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 337 阅读

相关洛谷P1181 数列分段Section I

题目描述对于给定的一个长度为N的正整数数列A\[i\]，现要将其分成连续的若干段，并且每段和不超过M（可以等于M），问最少能将其分成多少段使得满足要求。输入输出格

￡神魔★判官ぃ/ 2022年05月31日 11:19/ 0 赞/ 179 阅读

相关洛谷P1372 又是毕业季I

题目背景 “叮铃铃铃”，随着高考最后一科结考铃声的敲响，三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍，憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑和泪水，全

迈不过友情╰/ 2022年05月26日 13:15/ 0 赞/ 173 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 339 阅读

相关洛谷P1540——机器翻译

题目背景小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。题目描述这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义

傷城~/ 2022年04月14日 06:55/ 0 赞/ 320 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 369 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 459 阅读

相关洛谷 P1396 营救

　　　　　　　　　　　　　　　　　　　　[洛谷 P1396 营救][P1396] 题目描述 “咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查

怼烎@/ 2021年10月01日 00:04/ 0 赞/ 463 阅读