链接链接http://codeforces.com/gym/100729/attachments/download/3754/20112012-northwestern-european-regional-contest-nwerc-2011-en.pdf

题意:给你n

求出所有的C(m,k)=n

这一题..n<=10^15

所以做法就比较有趣了

首先就是可以得到一个规律

C的增长相当快,C(100,10)=17,310,309,456,440 > 1e15

那么我们可以考虑

对于k=1到10的时候,分别枚举,二分,求出一个对应的k

如果对于同一个n而言(n>100),k的增大(<50的情况下)只会让值变得更大

那么我们只要知道k在11~n-11之间几乎(好像也是完全)无解的

那么只要暴力枚举以后二分出m即可,注意去重

代码如下:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct answer
{
    long long x;
    long long y;
    friend bool operator < (const answer &a,const answer &b)
    {
        if (a.y!=b.y) return a.y<b.y;
        return a.x<b.x;
    }
    friend bool operator == (const answer &a,const answer &b)
    {
        return !((a<b)||(b<a));
    }
    void output()
    {
        cout<<"("<<y<<","<<x<<") ";
    }
};
answer ans[10005];
long long c[105][105];
long double check(long long x,int y)
{
    int i;
    long double t=0;
    for (i=1;i<=y;i++)
    {
        t+=log10((long double)(x+1-i));
        t-=log10((long double)i);
    }
    return t;
}
long long cc(long long x,int y)
{
    int i;
    long long t=1;
    for (i=1;i<=y;i++)
    {
        t*=(x+1-i);
        t/=i;
    }
    return t;
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t;
    scanf("%d",&t);
    int zu;
    int i,j;
    c[0][0]=1;
    for (i=1;i<=100;i++)
    {
        c[i][0]=1;
        for (j=1;j<=100;j++)
        {
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            if (c[i][j]>10000000000000000ll) c[i][j]=10000000000000000ll;
        }
    }
    for (zu=0;zu<t;zu++)
    {
        long long n;
        cin>>n;
        int i,j;
        int sum=0;
        for (i=0;i<=100;i++)
        {
            for (j=0;j<=100;j++)
            {
                if (c[i][j]==n)
                {
                    ans[sum].x=j;
                    ans[sum].y=i;
                    sum++;
                }
            }
        }
        for (i=1;i<=10;i++)
        {
            long long l=i,r=n;
            for (;l<=r;)
            {
                long long mid=(l+r)/2;
                if (check(mid,i)<=log10((long double)n))
                {
                    l=mid+1;
                }
                else
                {
                    r=mid-1;
                }
            }
            long long t=cc(r,i);
            if (t==n)
            {
                ans[sum].x=i;
                ans[sum].y=r;
                sum++;
                ans[sum].x=r-i;
                ans[sum].y=r;
                sum++;
            }
            t=cc(l,i);
            if (t==n)
            {
                ans[sum].x=i;
                ans[sum].y=l;
                sum++;
                ans[sum].x=l-i;
                ans[sum].y=l;
                sum++;
            }
        }
        sort(ans,ans+sum);
        sum=unique(ans,ans+sum)-ans;
        cout<<sum<<'\n';
        for (i=0;i<sum;i++)
        {
            ans[i].output();
        }
        cout<<'\n';
    }
    return 0;
}