Kattis之旅——Factovisors
The factorial function, n! is defined thus for n a non-negative integer:
We say that a divides b if there exists an integer k such that
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 = 76000; ll n, m, s, res, ans, len, T, k, num; int x, y; int pr[maxn]; void get_pr(){ int a[maxn] = {0}; len = 0; for(int i=2; i<maxn; i++) { if( a[i]==0 ) { pr[len++] = i; int j = i; while( j < maxn ) { a[j] = 1; j += i; } } } } bool judge(int x, int cnt) { int c = 0; ll t = n; while( t ) { c += t/x; t /= x; } return cnt<=c; } void input() { get_pr(); while( cin >> n >> m ) { if( m == 0 ) { printf("%lld does not divide %lld!\n",m,n); continue; } ll t = m; bool f = true; for(int i=0; i<len && pr[i]<=m; i++) { if( m%pr[i] == 0 ) { res = 0; while( m%pr[i]==0 ) { res ++; m /= pr[i]; } f = f&&judge(pr[i], res); } } if( m!=1 ) f = f&&judge(m, 1); if( f ) printf("%lld divides %lld!\n",t,n); else printf("%lld does not divide %lld!\n",t,n); } } int main(){ input(); return 0; }
