Factovisors
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
The input to your program consists of several lines, each containing two non-negative integers, n and m, both less than 2^31. For each input line, output a line stating whether or not m divides n!, in the format shown below.
Sample Input
6 96 2720 1000020 1000001000 1009
Output for Sample Input
9 divides 6!27 does not divide 6!10000 divides 20!100000 does not divide 20!1009 does not divide 1000!
题意：给出n和m，问m是否能整除n的阶乘。
分析：能够对m进行质因数分解，得到每一个素因子的个数。与n!中此因子的个数进行比較，若大于n!中此因子的个数。则不能整除。
#include#include #include const int MAXN = 100005;int vis[MAXN], prime[10000], num;void get_prime() //筛法求素数{ num = 0; memset(vis, 0, sizeof(vis)); for(int i = 2; i < MAXN; i++) { if(!vis[i]) { prime[num++] = i; for(int j = i + i; j < MAXN; j += i) vis[j] = 1; } }}int Cal(int w, int p) //计算w的阶乘中有多少个p{ int ans = 0; while(w) { w /= p; ans += w; } return ans;}bool judge(int n, int m){ int k = (int)sqrt(m+0.5); for(int i = 0; i < num && prime[i] <= k; i++) { if(m % prime[i] == 0) { int cnt = 0; while(m % prime[i] == 0) { cnt++; m /= prime[i]; } if(Cal(n, prime[i]) < cnt) return false; } } //此时若 m!=1，则m必为素数，假设n>=m。则m必然能够整除n! if(m > 1 && n < m) return false; return true;}int main(){ int n, m; get_prime(); while(~scanf("%d%d",&n,&m)) { if(judge(n, m)) printf("%d divides %d!\n", m, n); else printf("%d does not divide %d!\n", m, n); } return 0;}
版权声明：本文博客原创文章，博客，未经同意，不得转载。