10139.cpp

ACM University Valladolid 10139

using namespace std;

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define EPS 1e-11
#define inf ( 1LL << 31 ) - 1
#define LL long long

#define _rep( i, a, b, x ) for( __typeof(b) i = ( a ); i <= ( b ); i += x )
#define rep( i, n ) for( __typeof(n) i = 0; i < ( n ); ++i )
#define rrep( i, a, b ) for( __typeof(b) i = ( a ); i >= ( b ); --i )
#define xrep( i, a, b ) for( __typeof(b) i = ( a ); i <= ( b ); ++i )

#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define all(x) (x).begin(), (x).end()
#define ms(x, a) memset((x), (a), sizeof(x))
#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()

typedef vector <int> vi;

// She
// May be the reason I survive
// The why and wherefore I'm alive
// The one I'll care for through the rough in ready years

//...

vi b, p, prms;
int A, B;
const int MAX = 46350;
void S()
{
	int i, j;
	b = vi(MAX+1, 1);
	p.pb(2);
	for (i=3; i<=MAX; ++i)
	{
		if (b[i])
		{
			p.pb(i);
			for (j=i+i; j<=MAX; j+=i)
				b[j] = 0;
		}
	}
}

vi kactor(LL n)
{
	vi ret;
	int t;
//	cout<<sz(prms)<<endl;
	rep(i, sz(prms))
	{
		LL P = (int) prms[i], x = P;
		LL c = 0, ans = 0;
		if (x > (LL)B) break;
		while (x <= n)
		{
//			cout<<"hereis"<<endl;
			ans += n / x;
			x *= (LL)P;
		}
//		cout<<n<<' '<<P<<' '<<ans<<endl;
		ret.pb(ans);
	}
	return ret;
}


vi factor(int n)
{
	vi ret;
	prms = p;
	rep(i, sz(p))
	{
		int P = p[i];
		int c = 0;
		if (n <= 1) break;
		while (n%P == 0)
		{
//			cout<<"oh no!"<<endl;
			n /= P;
			c++;
		}
		ret.pb(c);
	}
	
	if (n != 1)
	{
		prms.pb(n);
		ret.pb(1);
	}
	
	return ret;
	
}

int main()
{
	vi x, y;
	S();
	
	int xx = 1;
	
	while (scanf("%d %d", &A, &B) == 2)
	{
		if (B == 0)
		{
			printf("0 does not divide %d!\n", A);
			continue;
		}
		
		if (A >= B)
		{
			printf("%d divides %d!\n", B, A);			
			continue;
		}
		
		if (B == 1)
		{
			printf("%d divides %d!\n", 1, A);			
			continue;
		}
		
		y = factor(B);
		x = kactor(A);
//		cout<<"out"<<endl;
		bool flag = true;
		rep(i, sz(y))
		{
			//cout<<prms[i]<<' '<<y[i]<<' '<<x[i]<<endl;
//			cout<<"blah"<<endl;
			if (prms[i] > B) break;
			if (x[i]<y[i])
			{
				flag = false;
				break;
			}
		}
		
		if (flag)
		{
			printf("%d divides %d!\n", B, A);			
		}
		else
		{
			printf("%d does not divide %d!\n", B, A);			
		}
		
	}
}