time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThe number “zero” is called “love” (or “l’oeuf” to be precise, literally means “egg” in French), for example when denoting the zero score in a game of tennis.
Aki is fond of numbers, especially those with trailing zeros. For example, the number 92009200 has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.
However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.
Given two integers nn and bb (in decimal notation), your task is to calculate the number of trailing zero digits in the bb-ary (in the base/radix of bb) representation of n!n! (factorial of nn).Input
The only line of the input contains two integers nn and bb (1≤n≤10181≤n≤1018, 2≤b≤10122≤b≤1012).Output
Print an only integer — the number of trailing zero digits in the bb-ary representation of n!n!ExamplesinputCopy
6 9
outputCopy
1
inputCopy
38 11
outputCopy
3
inputCopy
5 2
outputCopy
3
inputCopy
5 10
outputCopy
1
Note
In the first example, 6!(10)=720(10)=880(9)6!(10)=720(10)=880(9).
In the third and fourth example, 5!(10)=120(10)=1111000(2)5!(10)=120(10)=1111000(2).
The representation of the number xx in the bb-ary base is d1,d2,…,dkd1,d2,…,dk if x=d1bk−1+d2bk−2+…+dkb0x=d1bk−1+d2bk−2+…+dkb0, where didi are integers and 0≤di≤b−10≤di≤b−1. For example, the number 720720 from the first example is represented as 880(9)880(9) since 720=8⋅92+8⋅9+0⋅1720=8⋅92+8⋅9+0⋅1.
You can read more about bases here.
题目来源：https://codeforces.com/contest/1114/problem/C
题目大意：输入n与r，求解n！在r进制下末尾0的个数
解题思路：
（错误）在比赛中我是按照题意一步一步的做，计算阶乘取余计数，代码如下
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fact (ll n)
{
ll m=1;
for(int i=1; i<=n; i++)
{
m*=i;
}
return m;
}
int main()
{
ll r,n;
stack<int> s;
cin>>n>>r;
n=fact(n);
ll t = n;
int cnt=0;
while(n)
{
cnt++;
s.push(n%r);
n/=r;
}
cnt-=1;
ll sum = 0;
while(!s.empty())
{
//cout<<s.top()<<" ";
sum += s.top()*pow(r,cnt);
if(sum == t)
{
break;
}
cnt--;
s.pop();
}
cout<<cnt<<endl;
return 0;
}
错误的原因：应该是阶乘的数据太大了直接爆了，所以在38 11该样例直接输出-1了
求n!在b进制下末尾0的个数
思路：等价于n!%(b^k)==0的最大k
将b分解为若干素数乘积，记录每个素数含多少次方 b = p1^y1·p2^y2·…·pm^ym.
然后求n!种每个素数含多少次方n ! = p1^x1·p2^x2·…·pm^xm·
首先答案最小值ans必须赋很大1e18这样子，因为末尾的0个数可能非常非常多，赋个1<<50这样子都不行。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long n,b;
#define endl '
'
void input(){
cin >> n >>b;
}
void solve(){
ll ans = 1000000000000000000ll;
for(ll i=2; i<=b; i++){
if(1ll * i * i > b) i = b;
int cnt = 0;
while(b % i==0){
b/=i;
cnt++;
}
if( cnt == 0){
continue;
}
ll tmp = 0, mul =1;
while(mul <= n / i){
mul *=i;
tmp +=n /mul;
}
ans = min(ans,tmp/cnt);
}
cout << ans << endl;
}
int main(int argc, char* argv[]){
std::ios::sync_with_stdio(false);
cin.tie(0);
//C++的输入输出的兼容性,使得c++的速度和c一样
input(); solve(); return 0;
return 0;
}