(笔试题)N!的三进制数尾部0的个数

题目：

用十进制计算30!（30的阶乘），将结果转换成3进制进行表示的话，该进制下的结果末尾会有____个0。

思路：

这道题与上一篇博文N!尾部连续0的个数的思路是一样的。

计算N！下三进制结果末尾有多少个0，其实就是计算三进制中的3被连续进位多少次，只要将N！因式分解成3^m*other，m就是答案。

技巧性的解法就是：m=N/3+N/(3^2)+N/(3^3)....+N/(3^k) (k<=N/3)

（三进制数：第一位满3进1，第二位满9进1，第三位满27进1。。。）

代码：

#include <iostream>

using namespace std;

long long NumOfZero(long long n){

    long long count=0;

    while(n>0){

        count+=n/3;

        n=n/3;

    }

    return count;

}

int main()

{

    long long n=30;

    cout<<NumOfZero(n)<<endl;

    return 0;

}

巴特西

(笔试题)N!的三进制数尾部0的个数

最新文章

热门文章