阶乘题解

阶乘

https://ac.nowcoder.com/acm/contest/5505/C

题目为: 给定一个正整数 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;
    }
                  }