luogu1316：丢瓶蓋：排序+二分答案

題目連接配接

• 該題是luogu試煉場的2-12：T7

題目大意

1. 給出 n 個數字，表示數軸上的刻度；
2. 找出其中的 m 個，數字之間的跨度是 d ；
3. 要求 d 的最小值 ，盡可能大。

題目分析

• 經典二分題目，有一道異曲同工的：憤怒的牛
• 二分的精髓不在過程，而在最終對于L和R的處理！
• noi題庫有一個二分專題，10題讓你愉快入場！

解題思路：

1. 因為要選點，又是在數軸上，先排序比較穩當
2. 接下來是标準的二分答案+貪心查找

代碼1:

//luogu1029:最大公約數和最小公倍數問題

//1：公約數問題 
//2：輾轉相除法 

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

int n,m,ans=0;

int gcd(int x,int y)
{
	if(y==0) return x;
	return gcd(y,x%y);
}

int main()
{
	scanf("%d %d",&n,&m);
	
	int t=sqrt(n*m);
	int k=n*m;
	
	for(int i=1;i<=t;i++)
	{
		if( k%i==0 && gcd(i,k/i)==n) ans++;
	}
 	
 	printf("%d",ans*2);
 	
	return 0;
}