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 ...
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 231.
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!
m能否被n!整除，題目並不難，細節扣的多。分解m的質因數，然後通過勒讓德的結論就能過。
while（n）{
n/=x;
sum+=n;
}
被英語語法gank了一波，還要註意的是 0和1 也能整除。
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#define N 1000010
using namespace std;
int vis[N];
int prime[N];
int pn=0,flag;
void gp()
{
for (int i = 2; i <= N; i++) {
if (vis[i]) continue;
prime[pn++] = i;
for (int j = i; j <= N; j += i)
vis[j] = 1;
}
}
int lrd(int n,int x)
{
int sum=0;
while(n)
{
n/=x;
sum+=n;
}
return sum;
}
int main()
{
gp();
//cout<<prime[pn-1]<<endl;
int m,n;
while(~scanf("%d%d",&n,&m))
{
if((n>=m)||(n==0&&m==1))
{
printf("%d divides %d!\n",m,n);
continue;
}
flag=0;
int x=m;
for(int i=0;prime[i]*prime[i]<=m;i++)
{
int cnt=0;
while(x%prime[i]==0)
{
x/=prime[i];
cnt++;
}
if(cnt)
{
int res=lrd(n,prime[i]);
if(res<cnt)
flag=1;
}
}
if((x<=n&&!flag))
printf("%d divides %d!\n",m,n);
else
printf("%d does not divide %d!\n",m,n);
}
}
