欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Binomial coefficients UVA - 1649(枚举+二分)

程序员文章站 2022-03-11 21:00:23
...

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;
}

 

相关标签: 枚举