10139-uva

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MX = 100000;
bitset<MX> bs;
vector<int> primes ;
map<int,int> number_factors;


void sieve()
{
    bs.set();
    bs[0]=bs[1]=0;
    for(ll i=2;i<MX+1;i++)
        if(bs[i])
        {
            for(ll j=i*i;j<MX;j+=i) bs[j] = 0;
            primes.push_back(i);
        }
}

vector<int> findPrimes(ll N)
{
    vector<int> factors;
    ll idx = 0 , pf = primes[0];
    while(pf*pf<=N)
    {
        while(N%pf==0)
        {
            N/=pf;
            number_factors[pf]++;
        }
        pf=primes[++idx];
    }
    if(N!=1)number_factors[N]++;
    return factors;
}

ll get_power(ll n, ll p)
{
    int res =0;
    for(ll i=p;i<=n;i*=p)
        res+=n/i;
    return res;
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    long long n,m;
    sieve();
    while(cin>>n>>m)
    {
        bool verif = true;
        if(m>n){
            findPrimes(m);
            for(auto &it:number_factors)
            {
                if(get_power(n,it.first)<it.second)
                {
                    verif = false;
                    break;
                }
            }
            number_factors.clear();
        }
        if(verif)
            cout<<m<<" divides "<<n<<"!\n";
        else
            cout<<m<<" does not divide "<<n<<"!\n";
    }
    return 0;
}