仅有一行，为正整数m

输出仅有一个正整数，表示所有的满足f(n)=n,(n<=m) 的自然数的个数。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<unistd.h>using namespace std;typedef long long qword;#define MAXN 20100class number//四位{        public:                const static int max_val=10000;                const static int max_len=100;                number()                {                        clear();                }                number(int x)                {                        *this=x;                }                bool is_odd()const                {                        return numb[0]%2==1;                }                bool is_even()const                {                        return numb[0]%2==0;                }                int size()const                {                        return topn;                }                int length()const                {                        int x=numb[topn];                        int ret=0;                        while (x)                        {                                ret++;                                x/=10;                        }                        int y=0;                        x=number::max_val;                        while (x)                        {                                y++;                                x/=10;                        }                        y--;                        ret+=topn*y;                        return ret;                }                number pow(int x)const                {                        number ret,a;                        a=*this;                        ret=1;                        while (x)                        {                                if (x&1)ret=ret*a;                                a=a*a;                                x>>=1;                        }                        return ret;                }                void operator =(int x)//{{{                {                        int now=0;                        clear();                        numb[now]=x;                        while (numb[now]>=number::max_val)                        {                                numb[now+1]+=numb[now]/number::max_val;                                numb[now]%=number::max_val;                                now++;                                if (now>topn)topn=now;                        }                }//}}}void operator =(number num){        topn=num.topn;        memcpy((this->numb),num.numb,sizeof(num.numb[0])*(topn+1));}void operator +=(number num)//{{{{        int i;        topn=max(topn,num.topn);        for (i=0;i<=topn;i++)        {                numb[i]+=num.numb[i];;                if (numb[i]>=number::max_val)                {                        numb[i+1]+=numb[i]/number::max_val;                        numb[i]%=number::max_val;                }        }        while (numb[topn+1])        {                topn++;                numb[topn+1]+=numb[topn]/number::max_val;                numb[topn]%=number::max_val;        }}//}}}void operator +=(int x)//{{{{        int now=0;        if (topn==-1)topn=0;        numb[now]+=x;        while (numb[now]>=number::max_val)        {                numb[now+1]+=numb[now]/number::max_val;                numb[now]%=number::max_val;                now++;                if (now>topn)topn=now;        }}//}}}void operator *=(int x)//{{{{        int i;        for (i=0;i<=topn;i++)        {                numb[i]*=x;        }        for (i=0;i<=topn;i++)        {                if (numb[i]>=number::max_val)                {                        numb[i+1]+=numb[i]/number::max_val;                        numb[i]%=number::max_val;                }        }        while (numb[topn+1])        {                topn++;                numb[topn+1]+=numb[topn]/number::max_val;                numb[topn]%=number::max_val;        }}//}}}void operator -=(number &num)//{{{{        if (*this<num)throw "Error!\n->void operator -=(number &num)\n";        int i;        for (i=0;i<=topn;i++)        {                numb[i]-=num.numb[i];        }        for (i=0;i<=topn;i++)        {                while (numb[i]<0)                {                        numb[i]+=number::max_val;                        numb[i+1]--;                }        }        while (topn&&!numb[topn])topn--;}//}}}void operator --(int)//{{{{        if (topn==0&&numb[0]==0)throw "Error!\n->void operator --(int)\n";        int now=0;        numb[now]--;        while (numb[now]<0)        {                numb[now+1]--;                numb[now]+=number::max_val;        }        while (topn&&!numb[topn])topn--;}//}}}private:int numb[max_len];int topn;void clear(){        topn=0;        memset(numb,0,sizeof(numb));}friend bool operator <(number num1,number num2);friend bool operator <=(number num1,number num2);friend bool operator ==(number num1,number num2);friend ostream& operator <<(ostream &out,number num);friend istream& operator >>(istream &in,number &num);friend number operator *(number num1,number num2);friend number operator *(number num,int x);friend number operator +(number num1,number num2);//a=a+b远没有a+=b快};bool operator <(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)        {                return num1.topn<num2.topn;        }         int i;        for (i=num1.topn;i>=0;i--)        {                if (num1.numb[i]!=num2.numb[i])                {                        return num1.numb[i]<num2.numb[i];                }        }        return false;}//}}}bool operator <=(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)        {                return num1.topn<num2.topn;        }         int i;        for (i=num1.topn;i>=0;i--)        {                if (num1.numb[i]!=num2.numb[i])                {                        return num1.numb[i]<num2.numb[i];                }        }        return true;}//}}}bool operator ==(number num1,number num2)//{{{{        if (num1.topn!=num2.topn)return false;        for (int i=0;i<=num1.topn;i++)        {                if (num1.numb[i]!=num2.numb[i])return false;        }        return true;}//}}}ostream& operator <<(ostream &out,number num)//{{{{        int i;        out<<num.numb[num.topn];        for (i=num.topn-1;i>=0;i--)        {                //压六位时                //if (num.numb[i]<100000)out<<"0";                //if (num.numb[i]<10000)out<<"0";                if (num.numb[i]<1000)out<<"0";                if (num.numb[i]<100)out<<"0";                if (num.numb[i]<10)out<<"0";                out<<num.numb[i];        }        return out;}//}}}istream& operator >>(istream &in,number &num)//{{{{        string str;        in>>str;        int i;        num.clear();        for (i=(int)str.length()-1,num.topn=0;i>=0;i-=4,num.topn++)        {                if (i-3<(int)str.length())                {                        num.numb[num.topn]=(str[i]-‘0‘)+10*(str[i-1]-‘0‘)+100*(str[i-2]-‘0‘)+1000*(str[i-3]-‘0‘);                }else                {                        if (i-2<(int)str.length())num.numb[num.topn]+=100*(str[i-2]-‘0‘);                        if (i-1<(int)str.length())num.numb[num.topn]+=10*(str[i-1]-‘0‘);                        if (i<(int)str.length())num.numb[num.topn]+=(str[i]-‘0‘);                }        }        num.topn--;        return in;}//}}}number operator *(number num,int x)//{{{{        number ret;        ret=num;        ret*=x;        return ret;}//}}}number operator *(number num1,number num2){        number ret;        ret.topn=num1.topn+num2.topn;        for (int i=0;i<=num1.topn;i++)                for (int j=0;j<=num2.topn;j++)                {                        ret.numb[i+j]+=num1.numb[i]*num2.numb[j];                        ret.numb[i+j+1]+=ret.numb[i+j]/number::max_val;                        ret.numb[i+j]%=number::max_val;                }        for (int i=0;i<=ret.topn;i++)        {                ret.numb[i+1]+=ret.numb[i]/number::max_val;                ret.numb[i]%=number::max_val;        }        while (ret.numb[ret.topn+1])        {                ret.topn++;                ret.numb[ret.topn+1]+=ret.numb[ret.topn]/number::max_val;                ret.numb[ret.topn]%=number::max_val;        }        while (ret.topn && !ret.numb[ret.topn])        {                ret.topn--;        }        return ret;}number operator +(number num1,number num2)//{{{{        number ret;        ret=num1;        ret+=num2;        return ret;}//}}}char str[MAXN];int num0[MAXN];bool num[MAXN];number rec[MAXN][2][2];int n,m;number search_m(int now,int fl,int bo){        int x,y;        x=now-1;y=n-now;        if (x>y)        {                number ret;                ret=(int)(fl || (!fl && !bo));                return ret;        }        number &res=rec[now][fl][bo];        number aa;        if (aa<rec[now][fl][bo])return res;        res=0;        if (!fl)        {                if (num[y])                {                        //1                        if (num[x]==1)                                res+=search_m(now+1,false,bo);//1                        else                                res+=search_m(now+1,false,true);//1                        if (now>1)//首位非0                        {                                if (num[x]==1)                                        res+=search_m(now+1,true,false);//0                                else                                        res+=search_m(now+1,true,bo);//0                        }                }else if (!num[y])                {                        if (now>1)//特殊处理m==0情况                        {                                if (num[x]==1)                                        res+=search_m(now+1,false,false);//0                                else                                        res+=search_m(now+1,false,bo);//0                        }                }        }else        {                res+=search_m(now+1,true,true);//1                res+=search_m(now+1,true,true);//0        }        return res;}int main(){        //freopen("input.txt","r",stdin);        scanf("%s\n",str);        int i,j,x,y;        n=strlen(str);        x=y=-1;        for (i=n-1;i>=0;i-=4)        {                x++;                for (j=max(0,i-3);j<=i;j++)                        num0[x]=num0[x]*10+str[j]-‘0‘;        }        n=x+1;        x=0;        while (~n)        {                num[x++]=num0[0]%2;                for (i=n-1;i>=0;i--)                {                        if (i)num0[i-1]+=(num0[i]&1)*10000;                        num0[i]/=2;                }                while (n>=0 && !num0[n-1])n--;        }        n=x;        /*for (i=n-1;i>=0;i--)          {          printf("%d",num[i]);          }          printf("\n");*/        /*for (i=0;i<=n;i++)          for (j=0;j<2;j++)          for (k=0;k<2;k++)          rec[i][j][k]=-1;*/        number ans;        ans=search_m(1,false,false);        number xx;        for (i=1;i<n;i++)        {                xx=2;                xx=xx.pow((i-1)/2);                ans+=xx;        }        cout<<ans<<endl;        return 0;}