题目207：整数划分方程

欧拉计划

Integer partition equations

For some positive integers k, there exists an integer partition of the form   4^t = 2^t + k,
where 4^t, 2^t, and k are all positive integers and t is a real number.

The first two such partitions are 4¹ = 2¹ + 2 and 4^1.5849625... = 2^1.5849625... + 6.

Partitions where t is also an integer are called perfect.
For any m ≥ 1 let P(m) be the proportion of such partitions that are perfect with k ≤ m.
Thus P(6) = 1/2.

In the following table are listed some values of P(m)

   P(5) = 1/1
   P(10) = 1/2
   P(15) = 2/3
   P(20) = 1/2
   P(25) = 1/2
   P(30) = 2/5
   ...
   P(180) = 1/4
   P(185) = 3/13

Find the smallest m for which P(m) < 1/12345.

题目：

对一些正整数 k 来说，存在一个整数划分，它具有 4^t = 2^t + k 的形式，其中，4^t， 2^t，k 都是正整数而 t 则是实数。

前两个这样的划分分别是 4¹ = 2¹ + 2 和 4^1.5849625... = 2^1.5849625... + 6。

如果这个划分中的 t 值 也是整数的话，称之为完美划分。

对于任意大于等于 1 的 m，定义 P(m) 为 k ≤ m 得到的分割中，完美分割所占比例，

因此，P(6) = 1/2。

下表是一些列举的 P(m) 的值：

        P(5) = 1/1
        P(10) = 1/2
        P(15) = 2/3
        P(20) = 1/2
        P(25) = 1/2
        P(30) = 2/5
        ...
        P(180) = 1/4
        P(185) = 3/13

请给出满足 P(m) < 1/12345 的最小的 m 值。

fc1735

#include<stdio.h>
#define NUM 12345

int main()
{
        long start ;
        long count=0;
        for(start=2;;start++){
                long tmp=start;
                while(!(tmp&1)&&tmp!=1){
                        tmp>>=1;
                }
                count+=tmp==1?1:0;
                if(count*NUM<start-1)
                        break;
                
        }
        start<<=1;
        start--;
        start*=start;
        start--;
        start>>=2;
        printf("%ld",start);
}