2015年3月8日 星期日

[TIOJ 1443] 遞迴問題

作法:

由遞回式可以推出其實 f 的值就是 n 在二進制下有幾個 1 ,但這題 n 會到幾十萬位(題目也沒講QQ),我一開始就把大數模板拿過來揍他,結果TLE了,後來上網查才知道原來可以直接用 log 的性質作,因為要求的東西就是 log( n+1 )的整數部分,可以把 n+1 的 10 的次方都提乾淨再加回去。最後答案要加一個很小的浮點數修正誤差。

code :

#include<bits/stdc++.h>
#define DB long double
using namespace std;
const int maxn=1000000+10 ;
 
char s[maxn] ;
main()
{
    scanf("%s",s) ;
    int n=strlen(s),x ;
    for(x=n-1;s[x]=='9' && x>=0;x--) s[x]='0' ;
    if(x>=0) s[x]++ ;
    else
    {
        s[0]='1' ;
        s[n++]='0' ;
    }
 
    DB a=0.0 ;
    for(int i=0;i<n && i<40;i++) a += (s[i]-'0') * powl( 10.0, -i );
 printf( "%d\n", (int)(log2l(a)+(n-1)*log2l(10)+((DB)1e-10)) );
}
 
 

沒有留言:

張貼留言