因子 格式 nbsp 整数 100% ostream 没有 说明 出现
SOL君(炉石主播)和SOL菌(完美信息教室讲师)是好朋友。
SOL君很喜欢阶乘。而SOL菌很喜欢研究进制。
这一天,SOL君跟SOL菌炫技,随口算出了n的阶乘。
SOL菌表示不服,立刻就要算这个数在k进制表示下末尾0的个数。
但是SOL菌太菜了于是请你帮忙。
输入格式:
每组输入仅包含一行:两个整数n,k。
输出格式:
输出一个整数:n!在k进制下后缀0的个数。
- 10 40
- 2
对于20%的数据,n <= 1000000, k = 10
对于另外20%的数据,n <= 20, k <= 36
对于100%的数据,n <= 10^12,k <= 10^12
1.一组数据
2.K不会==1
3.现在std没有爆long long
4.对数据有问题联系icy (建议大家不要面向数据编程)
分析:k=10就是一个非常经典的问题,将n!分解质因数,看看有多少个5就可以了.现在考虑k≠10的情况,模拟一下进制转换,就是不断地%k,/k,我们就是要求一开始k能整除n!多少次.
n!,k过大,显然不能直接算,涉及到倍数,我们可以分解一下k,看看k的质因子是不是n!都有,并且n中的次数大于等于k中的次数.假设n!有一个因子p1,次数为b1,它在k中的次数为b2,每做一次除法就是b1-=b2,每次做除法后都必须保证k中的质因子n!都有,并且次数不能小于k中的.能做多少次除法呢?把相同质因子的次数相除,取个min就可以了.
还有一个问题:k可以直接分解质因数,但是n!就非常大了,我们根本算不出来,怎么才能统计k中的每个质因数在n!中出现的次数呢?对于一个质因数p,1~n个数中有n / p个数包含这个质因子,有n / (p ^ 2)个数包含p^2,也就是相当于包含了p.我们求出包含了p^i的个数,最后相加一下就是答案了.因为阶乘嘛,最后乘起来等于指数的相加.
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- long long n, k;
- long long cnt, p[1000010], tot[1000010], ans = 10000000000000000;
- void f(long long x)
- {
- for (long long i = 2; i * i <= x; i++)
- {
- if (x % i == 0)
- {
- p[++cnt] = i;
- while (x % i == 0)
- {
- tot[i]++;
- x /= i;
- }
- }
- }
- if (x != 1)
- {
- p[++cnt] = x;
- tot[x]++;
- }
- }
- long long cal(long long x, long long y)
- {
- //printf("%lld %lld\n", x, y);
- if (y > x)
- return 0;
- return x / y + cal(x / y, y);
- }
- int main()
- {
- scanf("%lld%lld", &n, &k);
- f(k);
- for (int i = 1; i <= cnt; i++)
- ans = min(ans, cal(n, p[i]) / tot[p[i]]);
- printf("%lld\n", ans);
- return 0;
- }
noip模拟赛 SAC E#1 - 一道中档题 Factorial
来源: http://www.bubuko.com/infodetail-2347232.html