厦门理工学院oj 1225 -- 琪露诺的完美算术教室(二)

假设$N!$N!在十进制下的结果为$n$n，则其从$m$m进制转化过来时，可以写作
$n = a \times m^k$n=a×mk
其中$a$a为$n$n在$m$m进制下最高位到第一个末尾0前一位的数转为十进制，$k$k为末尾0的个数
以$5!$5!在二进制下（1111000）为例，$5! = 15 \times 2^3$5!=15×23，其中$15$15的二进制表示为1111，末尾0的个数为3
又$m$m通过分解质因数，可以写成$p_1^{\alpha1}+p_2^{\alpha2}+...+p_{i}^{\alpha i}$p1α1​+p2α2​+...+piαi​，故有
$n = a \times (p_1^{\alpha1}+p_2^{\alpha2}+...+p_{i}^{\alpha i})^k$n=a×(p1α1​+p2α2​+...+piαi​)k
而$N!$N!也可通过分解质因数写成
$n = p_{1}^{\alpha1'}+p_{2}^{\alpha2'}+...+p_{j}^{\alpha j'}$n=p1α1′​+p2α2′​+...+pjαj′​
记$\alpha x' = min(\alpha1', \alpha2', ..., \alpha i')$αx′=min(α1′,α2′,...,αi′)，则$k = \alpha x' / \alpha x$k=αx′/αx
那么怎么取出$N!$N!里质数$p$p的个数呢，首先从$1\sim N$1∼N中取出$p$p倍数的个数，接着取出$p^2$p2倍数的个数…，直到$p^x>N$px>N
$\alpha = \lfloor \frac{N}{p} \rfloor + \lfloor \frac{N}{p^2} \rfloor + ...$α=⌊pN​⌋+⌊p2N​⌋+...
在这题里很容易观察出二进制下末尾0的个数即为$N!$N!中质因子2的个数

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

typedef long long LL;

using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        LL n;
        cin >> n;
        LL res = 0;
        while(n)
        {
            res += n / 2;
            n /= 2;
        }
        cout << res << endl;
    }
    return 0;
}