The factorial function, n! is defined thus for n a non-negative integer:
0! = 1
n! = n * (n-1)! (n > 0)
We say that a divides b if there exists an integer k such that
k*a = b
Input
The input to your program consists of several lines, each containing two non-negative integers, n and m, both less than 2^31.
Output
For each input line, output a line stating whether or not m divides n!, in the format shown below.
Sample Input
6 9
6 27
20 10000
20 100000
1000 1009
Sample Output
9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!
给一个整数n和一个数m，求n的阶乘是否可以整除m。
将m分解质因数，然后对每个质因数在n中进行判断是否含有相同或者更多。
//Asimple
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
ll n, m, s, res, ans, len, T, k, num;
int x, y;
int pr[maxn]; void get_pr(){
int a[maxn] = {};
len = ;
for(int i=; i<maxn; i++) {
if( a[i]== ) {
pr[len++] = i;
int j = i;
while( j < maxn ) {
a[j] = ;
j += i;
}
}
}
} bool judge(int x, int cnt) {
int c = ;
ll t = n;
while( t ) {
c += t/x;
t /= x;
}
return cnt<=c;
} void input() {
get_pr();
while( cin >> n >> m ) {
if( m == ) {
printf("%lld does not divide %lld!\n",m,n);
continue;
}
ll t = m;
bool f = true;
for(int i=; i<len && pr[i]<=m; i++) {
if( m%pr[i] == ) {
res = ;
while( m%pr[i]== ) {
res ++;
m /= pr[i];
}
f = f&&judge(pr[i], res);
}
}
if( m!= ) f = f&&judge(m, );
if( f ) printf("%lld divides %lld!\n",t,n);
else printf("%lld does not divide %lld!\n",t,n);
}
} int main(){
input();
return ;
}