Created
March 14, 2019 09:51
-
-
Save donjar/144a9c11970a0a139816b530170e978a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| template<class T1, class T2> | |
| using umap = unordered_map<T1, T2>; | |
| template<class T> | |
| using uset = unordered_set<T>; | |
| typedef long long ll; | |
| typedef unsigned long long ull; | |
| int main() { | |
| ios::sync_with_stdio(false); | |
| cin.tie(nullptr); | |
| cout.tie(nullptr); | |
| ll n, b; | |
| cin >> n >> b; | |
| umap<ll, ll> pfs; // prime factors of b | |
| // factorize b | |
| for (ll t = 2; t * t <= b; ++t) { | |
| while (b % t == 0) { | |
| if (pfs.count(t) == 0) { | |
| pfs[t] = 0; | |
| } | |
| pfs[t]++; | |
| b /= t; | |
| } | |
| } | |
| // special case, b is a prime | |
| if (b > 1) { | |
| ll t = b; | |
| if (pfs.count(t) == 0) { | |
| pfs[t] = 0; | |
| } | |
| pfs[t]++; | |
| b /= t; | |
| } | |
| // res is the answer | |
| ll res = n; | |
| for (auto p : pfs) { | |
| ll pr = p.first; | |
| ll mult = p.second; | |
| ll nclone = n; | |
| // get v_pr(n!) | |
| ll currres = 0; | |
| while (nclone > 0) { | |
| ll amount = nclone / pr; | |
| currres += amount; | |
| nclone = amount; | |
| } | |
| // divide v_pr(n!) by the multiplicity of pr in b | |
| res = min(res, currres / mult); | |
| } | |
| cout << res; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment