整除问题

[编程题]整除问题

热度指数：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

输出

算法知识视频讲解

philos

发表于 2021-03-03 19:59:46

思路首先暴力求出来 n 的阶乘肯定不行，那么我们可以把 a 给拆分成若干个质因子之积，然后看下 2 ~ n 中包含多少个对应的质因子，就能得出来最多可以整除 a 的多少次方。比如 a 中有质因子、、，2 ~ n 中有对应的质因子、... 个，那 k 的最大值也就是若干个 num 的最小值。展开全文

csyfZhang

发表于 2020-04-25 18:48:41

给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。https://blog.csdn.net/csyifanZhang/article/details/105754286↑更好的阅读体验首先阶乘范围太大，不能直接longlong。所以我们要找到整除的真正含义：首先，对于展开全文

健康快乐最重要

发表于 2020-03-19 12:47:52

因为阶乘不容易存储，所以要分块进行相除。比如：n=5：5!=5 * 4 * 3 * 2 * 1，a=2;a里边只有一个质因数2，所以我们要看5!里有几个质因数2。对5、4、3、2、1分别取质因数并相加，得到共有4/2/2和2/2三个质因数2，所以k=3.如果含有多个质因数，那么找n!中除以a的质因数展开全文

亚枫

发表于 2022-03-26 21:18:55

0. 题目含义：求解 n! 包含多少个因子a 1. 主要函数： void getPrime()：筛法求素数的模板代码 int getBiggestPrimeFactor(int a)：获取输入a分解的最大的质因数 int getFactorNum(int n, int factor)：核心函数，展开全文

niua8687

发表于 2023-02-11 13:09:25

n!=n*(n-1)*(n-2)...*3*2a^k=a*a*a...*a1.把2~n进行质因数分解2.把a进行质因数分解3.看把2~n分解的质因数里包含多少倍的a的质因数 #include "stdio.h" #include "string.h" #include "limits.h" int 展开全文