单点时限: 2.0 sec
内存限制: 256 MB
双阶乘是一个数学概念,用 N!!
表示。当 $N$ 是自然数时,$N$ 的双阶乘表示不超过这个正整数 $N$ 且与 $N$ 有相同奇偶性的所有正整数乘积。
如,3!!=1×3=3,5!!=1×3×5=15,6!!=2×4×6=48,8!!=2×4×6×8=384
。
请计算给定两个自然数 $N$ 和 $M$,$M$ 为 N!!
的分解质因数后的一个因子,求 N!!
分解质因数后因子 $M$ 的个数。
当输入 $N$ 为 $6$,$M$ 为 $2$ 时,$6!!=2×4×6=2^4×3$,输出因子 $2$ 的个数为 $4$。
第 $1$ 行:一个整数 T(1≤T≤10)为问题数。
第 $2$ ~ $T+1$ 行:每个问题占一行,每行输入两个自然数:N(1<N≤10000)和一个因子$M$(数据保证$M$是$N!!$的质因子)。
对于每个问题,输出一行问题的编号($0$ 开始编号,格式:case #0:
等)。然后对应每个问题在一行中输出N!!质因数分解后因子M的个数。
3 8 2 15 5 999 3
case #0: 7 case #1: 2 case #2: 251