s! 在 K 进制下 最后有多少个0
分解质因数
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; int const MAXN = 1000; bool prime[MAXN]; char str[MAXN]; void Judge_Prime(){ memset(prime,false,sizeof(prime)); for(int i = 2;i < MAXN;i++){ if(!prime[i]){ for(int j = 2 * i;j < MAXN;j += i){ prime[j] = true; } } } } ll Get_S(int k){ int len = strlen(str); ll base = 1,sum = 0; for(int i = len - 1;i >= 0;i--){ int a; if(str[i] >= 'A' && str[i] <= 'Z') a = str[i] - 'A' + 10; else if(str[i] >= 'a' && str[i] <= 'z') a = str[i] - 'a' + 36; else a = str[i] - '0'; sum += a * base; base *= k; } return sum; } ll Calc(int i,ll s){ ll ret = 0; ll base = i; while(s >= i){ ret += s / i; s /= i; } return ret; } int main(){ Judge_Prime(); int k; while(~scanf("%s%d",str,&k)){ ll s = Get_S(k); cout<<s<<endl; ll ret = -1; for(int i = 2;i <= k;i++){ if(k % i == 0 && !prime[i]){ int a = 0,temp = k; while(temp % i == 0){ a++; temp /= i; } ll b = Calc(i,s); if(ret == -1 || ret > (b / a)) ret = b / a; } } cout<<ret<<endl; } return 0; } /* F4 46 1111111 62 */