阶乘 题解
阶乘
https://ac.nowcoder.com/acm/contest/5505/C
题目为: 给定一个正整数 p
求一个最小的正整数 n，使得 n! 是 p 的倍数
求一个最小的正整数 n，使得 n! 是 p 的倍数
大家是否还记得我们初高中学习的一个东西叫做质因数，就比如说6中的质因数为2和3，因为2*3等于6，其中6当中只有1个2和一个3，而8中有3个2组成为2*2*2=8；
所以要找到n，就必须使阶乘n中的大于对应p中所有质因数的个数。就比如4！中有7个2，就比8中的三个2多，4!就可以是8的倍数。
首先我们要求出p中质因数的种类以及每种种类的个数；我定义了一个f函数来完成，注意如果for完p还是>1的话，记得记录一下这个质因数。
然后用二分查找最小的那个n符合n!是p的倍数。
最关键的来了,有些小伙伴可能会问了，怎样检查n!是p的倍数呢？我在这用了一个check函数。
这是最关键性的代码了.
public static boolean check(int n)
{
int nums=0;
int x=n;
for(int i=1;i<=k;i++)
{
x=n;
nums=0;
while(x>0)
{
nums+=x/zhiyin[i];
x/=zhiyin[i];
}
if(zhiyinshu[i]>nums)
return false;
}
return true;
} 乍一看可能会看不太懂，这里我给大家举一个例子. 比如我们寻找8！中有多少个2.
因为8/2=4 4/2=2 2/2=1 所以8！当中有4+2+1=7个2，不信大家可以自己计算一下，8中有3个2,6中有1个2,4中有2个2,2中有1个2,3+1+2+1=7.
是不是感觉很神奇，这里相关问题还是不明白的话就询问度娘吧。
然后我们可以检查一下p质因数每个种类的个数是否小于等于对应n！中质因数的个数，全部都小于等于的话就符合条件啦，如果有一个大于的话当然就要返回false了。
代码如下
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
public static int zhiyin[] = new int[10000];
public static int zhiyinshu[] = new int[10000];
public static int k;
public static void main(String args[])throws IOException
{
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
in.nextToken();
int T = (int)in.nval;
int n,a,b;
for(int t=0;t<T;t++)
{
in.nextToken();
n = (int)in.nval;
Arrays.fill(zhiyin,0);
Arrays.fill(zhiyinshu,0);
out.println(f(n));
out.flush();
}
}
public static int f(int n)
{
k=0;
int N=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0)
{
zhiyin[++k] = i;
while(n%i==0)
{
zhiyinshu[k]++;
n/=i;
}
}
}
if(n>1)
{
zhiyin[++k] = n;
zhiyinshu[k]++;
}
int l=1,r=1000000009,mid,min=0;
while(l<=r)
{
mid = (l+r)>>1;
if(check(mid)==true)
{
min = mid;
r = mid-1;
}
else{
l = mid+1;
}
}
return min;
}
public static boolean check(int n)
{
int nums=0;
int x=n;
for(int i=1;i<=k;i++)
{
x=n;
nums=0;
while(x>0)
{
nums+=x/zhiyin[i];
x/=zhiyin[i];
}
if(zhiyinshu[i]>nums)
return false;
}
return true;
}
}
远景公司福利 157人发布
