題目背景
“叮鈴鈴鈴”，隨著高考最后一科結(jié)考鈴聲的敲響，三年青春時光頓時凝固于此刻。畢業(yè)的欣喜怎敵那離別的不舍，憧憬著未來仍毋忘逝去的歌。1000多個日夜的歡笑和淚水，全凝聚在畢業(yè)晚會上，相信，這一定是一生最難忘的時刻！

題目描述
為了把畢業(yè)晚會辦得更好，老師想要挑出默契程度最大的k個人參與畢業(yè)晚會彩排。可是如何挑呢？老師列出全班同學的號數(shù)1，2，……，n，并且相信k個人的默契程度便是他們的最大公約數(shù)（這不是迷信哦~）。這可難為了他，請你幫幫忙吧！

PS：一個數(shù)的最大公約數(shù)即本身。

輸入輸出格式

輸入格式：
兩個空格分開的正整數(shù)n和k。（n>=k>=1）

輸出格式：
一個整數(shù)，為最大的默契值。

輸入輸出樣例

輸入樣例#1： 復制
4 2
輸出樣例#1： 復制
2

【數(shù)據(jù)范圍】
對于20%的數(shù)據(jù)，k<=2,n<=1000
對于另30%的數(shù)據(jù)，k<=10,n<=100
對于100%的數(shù)據(jù)，k<=1e9,n<=1e9（神犇學校，人數(shù)眾多）
.
.
.
.
.
.

分析

此題簡化后，求的是：從1~n中取k個數(shù)，使這k個數(shù)的最大公約數(shù)最大
因為兩個數(shù)成倍數(shù)關(guān)系時，它們的最大公因數(shù)是兩數(shù)中的較小數(shù)，也就是相對來說公因數(shù)較大
返回題目，這k個數(shù)其實就是：x*1,x*2……x*k（但他們的和加起來不能超過n），那么能明顯，x就是答案了。
.
.
.
.
.
.
.

程序：

#include<iostream> using namespace std; long long n,k; int main() {cin>>n>>k;cout<<n/k;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/9499986.html

總結(jié)

以上是生活随笔為你收集整理的又是毕业季I的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。