Binomial coefficients UVA - 1649（枚举+二分）

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

typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define per(i,a,b) for(ll i=b-1;i>=a;i--)
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)

const int maxn=1e5+10;
const double eps=1e-8;

struct Ans{
    ll l,r;
    Ans(ll _l=0,ll _r=0):l(_l),r(_r){}
    bool operator<(const Ans& obj)const{
        if(l==obj.l)return r<obj.r;
        return l<obj.l;
    }
    bool operator==(const Ans& obj)const{
        return l==obj.l&&r==obj.r;
    }
}res[maxn];

/*
心态爆炸的题：看见大数就头疼
思想:
考虑C(n,m)=1e15,m最多也就是30(距离两端)左右，--->考虑枚举k,然后二分寻找K
特点:
C(n,m)也是暴增的特别厉害，所以发现K,会很小的
*/


int check(ll n,ll k,ll m){
    //解决C(n,k)溢出long long 的问题
    //1.计算C(n,k)不是很现实，我们可以用m去除以
    //2.我们可以用double类型来存储过程中的值，尽管有误差，但是没有什么太大的问题
    double sum=1;
    k=min(k,n-k);
    for(ll i=1;i<=k;i++){
        sum=sum*1.0*(n-i+1)/(1.0*i);
       // printf("i:%lld n:%lld k:%lld sum:%.2f\n",i,n,k,sum);
        if(sum>1.0*m+10.0)return 1;
    }
    //printf("n:%lld k:%lld sum:%.2f\n",n,k,sum);
    if(fabs(sum-1.0*m)<eps)return 0;
    return sum<m?-1:1;
}

/*
int check(ll n,ll k,ll m){
    //计算C(n,k)不是很现实，我们可以用m去除以
    ll sum=1;//printf("n:%lld k:%lld sum:%lld\n",n,k,sum);
    k=min(k,n-k);
    for(int i=1;i<=k;i++){
       if(m*i/(n-i+1)/sum==0)return 1;
       sum=sum*(n-i+1)/i;//!!!组合数一定得这么写，千万不要给我用什么*=（），这样后面就是0
    }
    return sum==m?0:-1;
}
*/
/*
2
2
15
*/

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        ll m;
        scanf("%lld",&m);
        int cnt=0;
        for(ll k=1;k<=30;k++){
            ll l=k,r=m,mid,ans=-1;
            while(l<=r){
               // printf("***K：%lld\n",k);
                mid=(l+r)>>1;
               // printf("l:%lld mid:%lld r:%lld\n",l,mid,r);
                int fk=check(mid,k,m);
                if(!fk){
                    ans=mid;break;
                }
                else if(fk>0) r=mid-1;
                else l=mid+1;
            }
            if(ans!=-1){
                res[cnt++]=Ans(ans,k);
                res[cnt++]=Ans(ans,ans-k);
            }
        }
        sort(res,res+cnt);
        cnt=unique(res,res+cnt)-res;
        printf("%d\n",cnt);
        rep(i,0,cnt) printf("(%lld,%lld)%c",res[i].l,res[i].r,i==cnt-1?'\n':' ');
    }
    return 0;
}