Algorithm - Problem - 又是毕业季I

又是毕业季I 洛谷 P1372

问题描述

“叮铃铃铃”,随着高考最后一科结考铃声的敲响,三年青春时光顿时凝固于此刻。毕业的欣喜怎敌那离别的不舍,憧憬着未来仍毋忘逝去的歌。1000多个日夜的欢笑和泪水,全凝聚在毕业晚会上,相信,这一定是一生最难忘的时刻!
为了把毕业晚会办得更好,老师想要挑出默契程度最大的k个人参与毕业晚会彩排。可是如何挑呢?老师列出全班同学的号数 1,2,,n1, 2, \cdots, n,并且相信 kk 个人的默契程度便是他们的最大公约数(这不是迷信哦~)。这可难为了他,请你帮帮忙吧!

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

输入

两个空格分开的正整数 nnkk。(nk1n\geqslant k\geqslant 1

输出

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

样例输入
1
4 2
样例输出
1
2

数论问题

分析

题目本质是求在 11nn 中选取 kk 个数的最大公约数的最大值.
(如果真的没有想到如何推导,对于本题应该采用找规律的手段)
我们设某个最大公约数为 tt,则第 ii 个数可以写成 aita_it,(1ik1\leqslant i\leqslant k).
为了方便处理,我们规定 1i<jk1\leqslant i < j\leqslant k 时有 ai<aja_i < a_j.

i,j:1i<jk,ai<aji:1ik,ai1,aitni:1ik,aikktntnktnk\begin{aligned} & \forall i,j:1\leqslant i<j\leqslant k, a_i < a_j\\ \wedge &\forall i:1\leqslant i\leqslant k,a_i\geqslant1, a_it\leqslant n\\ \Rightarrow & \exists i:1\leqslant i\leqslant k,a_i\geqslant k\\ \Rightarrow & kt\leqslant n\\ \Rightarrow & t\leqslant \frac{n}{k}\\ \Rightarrow & t\leqslant \left\lfloor \frac{n}{k}\right\rfloor \end{aligned}

上述证明只是说明了 tt 有界,最好将 nk\left\lfloor\frac{n}{k}\right\rfloor 进行验证一下,就可得出正确结果.

代码
1
2
3
4
5
6
7
8
9
#include <iostream>

int main()
{
int n, k;
std::cin >> n >> k;
std::cout << n / k;
return 0;
}