10139 - Factovisors

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()

map<int, int> factorize(int x) {
    map<int, int> fact_freq;
    if (x == 0) return fact_freq;
    while (x % 2 == 0) {
        fact_freq[2]++;
        x /= 2;
    }
    for (int i = 3; i <= sqrt(x); i += 2) {
        while (x % i == 0) {
            x /= i;
            fact_freq[i]++;
        }
    }
    if (x > 2) {
        fact_freq[x]++;
    }
    return fact_freq;
}

void $_$(int n, int m) {
    auto fact_freq = factorize(m);
    bool flag = true;
    for (auto& [p, cnt] : fact_freq) {
        int pow = 0;
        for (ll j = p; j <= n; j = j * p) {
            pow += n / j;
        }
        flag &= (pow >= cnt);
    }
    cout << m << " " << (flag ? "divides" : "does not divide") << " " << n << "!\n";
}

int main() {
    cin.tie(0), cin.sync_with_stdio(0);
    int test = 1, n, m;
    //cin >> test;
    while (cin >> n >> m) $_$(n, m);
}