Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.1 kB
1
Indexable
Never
#include <bits/stdc++.h>
#define fst first
#define snd second
#define int64 long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, b, a) for(int i = b; i >= a; i--)
 
using namespace std;
 
typedef pair<int,int> ii;
 
template<class X, class Y> bool maximize(X &a, Y b)
{
    if(a >= b) return false;
    a = b;
    return true;
}
 
template<class X, class Y> bool minimize(X &a, Y b)
{
    if(a <= b) return false;
    a = b;
    return true;
}
const int N = 1e6 + 66;

int cnt[N];

int main () {

	int n, m;
	cin >> n >> m;
 	
 	for(int i = 2; i <= n; i++) {
 		int current = i;
 		for(int j = 2; j * j <= current; j++) {
 			while(current % j == 0) {
 				cnt[j]++;
 				current /= j;
 			}
 		}
 		if(current > 1) cnt[current]++;
 	}

 	int res = 1e9;

 	for(int i = 2; i <= m; i++) {
 		if(m % i == 0) {
 			int d = 0;
 			while(m % i == 0) {
 				m /= i;
 				d++;
 			}

 			if(d > cnt[i]) {
 				cout << "-1\n";
 				return 0;
 			}
 			res = min(res, cnt[i] / d);
 		}
 	}	
 	cout << res;
}
Leave a Comment