整除问题

[编程题]整除问题

热度指数：14046 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。

输入描述:

两个整数n(2<=n<=1000)，a(2<=a<=1000)

输出描述:

一个整数.

示例1

输入

6 10

输出

算法知识视频讲解

Java

无问西东gmy

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            BigInteger fac_n = new BigInteger("1"); //n的阶乘（n!）
            for (int i = 2; i <= n; i++)
                //fac_n *= i;
                fac_n = fac_n.multiply(new BigInteger(String.valueOf(i)));
            BigInteger a = new BigInteger(in.next());
            BigInteger a_k = new BigInteger("1");   //a^k（a的k次方）
            BigInteger zero = new BigInteger("0");
            for (int k = 0;; k++) {
                BigInteger old_a_k = new BigInteger(a_k.toString());    //a^k
                a_k = a_k.multiply(a);  //a^(k+1)
                if (fac_n.mod(old_a_k).equals(zero)
                        && !fac_n.mod(a_k).equals(zero)) {
                    //n! % a^k == 0 && n! % a^(k+1) != 0
                    System.out.println(k);
                    break;
                }
            }
        }
    }
}

编辑于 2024-02-07 20:41:33 回复(0)

Java

哈哈群岛参上

import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigInteger n=sc.nextBigInteger();
BigInteger a = sc.nextBigInteger();
BigInteger sum = new BigInteger("1");
BigInteger i = new BigInteger("1");
BigInteger z= new BigInteger("1");
BigInteger k= new BigInteger("1");
int k1=1;
BigInteger zer = new BigInteger("0");

   while(i.compareTo(n)==-1||i.compareTo(n)==0)
   {
    sum=sum.multiply(i);
    i=i.add(z);
   }
while(k.compareTo(n)==-1)
{
if(sum.mod(a.pow(k1)).equals(zer))
{int p=k1+1;
  if(!sum.mod(a.pow(p)).equals(zer))
  {
   System.out.println(k);
   break;
  }
}
k=k.add(z);
k1++;
}
}
}

发表于 2020-03-30 11:27:15 回复(0)

Java

苡咩咩

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	public static void main(String[] args)
	{
		int n,a;
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext())
		{
			n = sc.nextInt();
			a = sc.nextInt();
			BigInteger num = BigInteger.ONE;
			for(int i = 2;i <= n;i ++)
				num = num.multiply(BigInteger.valueOf(i));
			int t = 0;
			BigInteger d = BigInteger.valueOf(a);
			while(num.compareTo(BigInteger.ZERO) == 1 && num.mod(d).compareTo(BigInteger.ZERO) == 0)
			{
				t ++;
				num = num.divide(d);
			}
			System.out.println(t);
		}
	}
	
}

发表于 2020-03-11 18:10:54 回复(0)