题目207：整数划分方程
Integer partition equationsFor some positive integers k, there exists an integer partition of the form 4t = 2t + k,
where 4t, 2t, and k are all positive integers and t is a real number.
The first two such partitions are 41 = 21 + 2 and 41.5849625... = 21.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 来说，存在一个整数划分，它具有 4t = 2t + k 的形式，其中，4t， 2t，k 都是正整数而 t 则是实数。
前两个这样的划分分别是 41 = 21 + 2 和 41.5849625... = 21.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 值。
#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);
}
页:
[1]