codeforces div2 603 C. Everyone is a Winner!(二分)

题目链接:https://codeforces.com/contest/1263/problem/C

题意:给你一个数字n,求n/k有多少个不同的数

思路:首先K大于n时,n/k是0。然后k取值在1到n之间的时候进行二分即可求解。

          举个例子,比如n = 11,那么k分别取值1 2 3 4 5 6 7 8 9 10 11时候,n/k是 11 5 3 2 2 1 1 1 1 1 1,因为n/k这组数据是具有单调性的,那么我们就可以在n/k这个取值范围内二分查找,每次查找到的不同的取值存起来,最终输出即可

代码:

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cstring>
using namespace std;
typedef long long ll;
int main(){
	int t;cin>>t;
	while(t--){
		ll n;cin>>n;
		ll pos = n;
		vector<ll> ans;
		ans.push_back(0);
		ans.push_back(1); 
		ll cur = n;//表示当前二分区间的右端点
		while(cur!=1){
			ll l = 1,r = cur;// 1 2 3 4 5 6 7 8 9 10 11
			                 // 11 5 3 2 2 1 1 1 1 1 1
			while(l<=r){
				ll mid = l + ((r - l) >> 1);
				                // 1 6
				                //  4 6
				                //  5 6
				                //  6 6 
				if(n/mid<=ans[ans.size() -1]){
					r = mid-1;
				}
				else if(n/mid>ans[ans.size() -1]){
					l = mid+1;
				}
			}
			ans.push_back(n/r);
			cur = r;  
		}
		cout<<ans.size()<<endl;
		for(int i = 0;i<ans.size() ;i++){
			cout<<ans[i]<<" ";
		}
		cout<<"
";
	}
	// 1 2 3 4 5 
	// 1 2 5
	return 0;
}
原文地址:https://www.cnblogs.com/AaronChang/p/12129617.html