c - 给定某个整数 N，有多少个基数 b 使得 N 的基数 b 表示以 1 开头？

Question

这个问题是在 codechef 竞赛之一中提出的。我已经在 c 中尝试过了。下面是我的代码:

    scanf("%d",&N);
    count=0;
    for(i=2;i<=N;i++)
    {

        c=a;
        while(c>=i)
           {
               c=c/i;
           }
           if(b==1)
             count++;
    }

    printf("%d\n",count);

但这只给了我部分分数。能在更短的时间内解决吗？如果是这样，怎么办？

Answer 1

基数 b 中以 1 和 d 数字开头的最小数字是 10...0，即 b^ (d-1).

最大的数字是2*b^(d-1)-1。因此，给定数字 N 落在该范围内的基数由不等式给出

pow(0.5*(N+1), 1.0/(d-1) ) <= b <= pow(N, 1.0/(d-1) )

通过适当的舍入，考虑随机浮点误差，您可以直接计算有多少个整数 b 在这些边界内。