UVa 1649

The link of the problem is below Code first:

#include <iostream>
#include <cmath>
#include <deque>
using namespace std;
deque< pair<unsigned long long,unsigned long long> >ans; 
int main()
{
    int t;   cin>>t;
    while(t--)
    {
        ans.clear();
        unsigned long long m,now=1,c=1;
        cin>>m;
        while(1)
        {
            c*=now; 
            unsigned long long w=pow(m,1.0/now)*pow(c,1.0/now)+1; 
            while(w--)
            {
                long double acu=1;
                for(unsigned long long i=1;i<=now;i++) 
                {acu=(long double)acu/i;  acu=(long double)acu*(w+i); }
                unsigned long long hi=(unsigned long long )floor(acu+1e-8);
                if(hi==m) 
                {   
                    if(!((w+now)%2==0 && now==(w+now)/2)) ans.push_front(pair<unsigned long  long,unsigned long long>(w+now,w+now-now));
                    ans.push_front(pair<unsigned long  long,unsigned long long>(w+now,now));
                }   
                if(acu<m) break;
            }
            if(w<=now++) break;
        }
        cout<<ans.size()<<endl;
        for(size_t i=0;i<ans.size();i++) cout<<"("<<ans[i].first<<","<<ans[i].second<<")"<<((i==ans.size()-1)?"":" ") ;
        cout<<endl; 
    }

    return 0;
}

式C(n,k)=(n*n-1*n-2*...*n-k+1)/kを用いる!構想はkを列挙し、nを迅速に見つけようとすることである.テクニックは:C(n,k)=C(n,n-k)私達はただ前の値だけに関心を持つため、境界はk>(n-k+1);Pow関数でnを推定して、pow関数の中で直接m*cを推定することができなくて、ULLさえ耐えられません;wはきっとn~n-k+1の間で、(実際にこの値を計算して末端からもっと近い)ため、絶えずwの値を減らして、1つのacu=mがあるかどうかを見ます
最後にw+1*w+2*...*w+k気をつけて1/3*3!=1のトラップ(+1 e-8)Ps:thanks for Vfleaking’s help Link:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=851&page=show_problem&problem=4524
文章に何か間違いがあったり、何か問題があったりしたら、ブロガーに教えてください:QQ:812483101