数学 2015百度之星初赛2 HDOJ 5255 魔法因子

 /*

     数学：不会写，学习一下这种解题方式:)

     思路：设符合条件的数的最高位是h，最低位是l，中间不变的部分为mid，由题意可得到下面的公式(这里对X乘上1e6用a表示，b表示1e6)

         (h*power+l+mid)*a = (l*power+h+mid)*b

         可推得：mid = ((h*power+l) * a - (l*power+h) * b) / (a - b);

         所以可以枚举h，l然后求mid，注意mid的最低位一定是0，因为留出最低位加l或者h

     详细解释：http://blog.****.net/u010660276/article/details/46290703

 */

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <cmath>

 #include <vector>

 using namespace std;

 typedef long long ll;

 const int MAXN = 1e4 + ;

 const int INF = 0x3f3f3f3f;

 vector<ll> V;

 int main(void)        //2015百度之星初赛2 HDOJ 5255 魔法因子

 {

     int t, cas = ;    scanf ("%d", &t);

     while (t--)

     {

         V.clear ();

         double x;    scanf ("%lf", &x);

         ll a = (ll) (x * 1e6 + 0.1);    ll b = 1e6;

         for (int k=; k<=; ++k)

         {

             ll p = ;    for (int i=; i<k; ++i)    p *= ;

             for (int r=; r<=; ++r)

             {

                 for (int l=; l<=; ++l)

                 {

                     ll tmp = (l * p + r) * b - (r * p + l) * a;

                     if (tmp % ( * (a - b)) == )

                     {

                         ll mid = tmp /  / (a - b);    ll tmp_mid = mid;

                         if (tmp_mid < )    continue;

                         int cnt = ;    while (tmp_mid)    {++cnt;    tmp_mid /= ;}

                         if (cnt <= k - )    V.push_back (r * p + mid *  + l);

                     }

                 }

             }

         }

         printf ("Case #%d:\n", ++cas);

         printf ("%d\n", V.size ());

         for (int i=; i<V.size (); ++i)

         {

             printf ("%I64d%c", V[i], (i == V.size ()-) ? '\n' : ' ');

         }

     }

     return ;

 }

 /*

 3

 3.1312

 3.1215

 0.3

 */