56 - 阶乘因式分解(一)
内存限制: 64MB 时间限制: 3000ms Special Judge: No
accepted:15 submit:16
题目描述:
给定两个数 m,n, 其中 m 是一个素数.
将 n(0<=n<=10000)的阶乘分解质因数, 求其中有多少个 m.
输入描述:
第一行是一个整数 s(0<s<=100), 表示测试数据的组数
随后的 s 行, 每行有两个整数 n,m.
输出描述:
输出 m 的个数.
样例输入:
复制 2 100 5 16 2
样例输出:
24
15
分析:
1, 其实就是看 [1, n] 中有多少个 m, m^2, m^3...
2, 将得到的对应 m, m^2, m^3 的个数累加, 即就是因式分解后质数 m 的最终个数
核心代码:
- while(n> m)
- {
- cnt += n / m;
- n /= m; // 除一次 m 相当于 m 自乘了一次
- }
C/C++ 代码实现(AC):
- #include <iostream>
- #include <algorithm>
- #include <cstring>
- #include <cstdio>
- #include <cmath>
- #include <stack>
- #include <map>
- #include <queue>
- #include <set>
- using namespace std;
- int main()
- {
- int t;
- scanf("%d", &t);
- while(t --)
- {
- int n, m, cnt = 0;
- scanf("%d%d", &n, &m);
- while(n>= m)
- {
- cnt += n / m;
- n /= m;
- }
- printf("%d\n",cnt);
- }
- return 0;
- }
nyoj 56 - 阶乘因式分解(一)(数学)
来源: http://www.bubuko.com/infodetail-2622945.html