P1284 整除问题 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2026年3月2日 15:28

整除问题题解：

P1284

回复 0 | 赞 11 | 浏览 228

#include<bits/stdc++.h> using namespace std; map<int,int> mp1,mp2; void factor(int n , map<int,int> &mp){ for(int i = 2; i <= sqrt(n); i++){ if(n % i == 0){ while(n % i == 0){ &...

岸上的乌龟

2026年2月12日 18:16

整除问题题解：

P1284

回复 0 | 赞 5 | 浏览 230

#include <bits/stdc++.h> using namespace std; int prime[1000]= {0}; void getprime() { prime[1]=1; for(int i=2; i<1000; i++) { if(prime[i]==0) { &...

2023年2月16日 14:41

详细题解（站在巨人的肩膀上）

P1284

回复 2 | 赞 159 | 浏览 7.0k

此题解是对前面题解的详细解答。（是看了各位大神的代码才知道怎么写的，自己想我大概是想不出来的，感谢各位佬）题干：给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。（这是幂运算，别看成乘法。）两个整数n(2<=n<=1000)，a(2<=a<=1000)。看一眼范围可以知道这个数的阶乘很大，一些类型会爆掉。既然会爆掉，那肯定不是正常的写法，再看这题是出现在分解素因数的章节，那自然要往上面想。。再看题干，先考虑整除。既然是整除，那么有两点，①取模==0 or ② n！>= a 时候相除为整数。至于用到那...

2026年2月5日 21:03

整除问题题解：经典的阶乘质因数分解问题

P1284

回复 1 | 赞 12 | 浏览 253

#include<bits/stdc++.h> using namespace std; // 计算 n! 中质数 p 的个数 int countInFactorial(int n, int p) { int count = 0; while(n) { n /= p; count += n; } return count; } int main() { int n, a; while(cin >> n >> a) { ...

2026年2月5日 16:30

整除问题题解：用 map 对比

P1284

回复 0 | 赞 5 | 浏览 144

关键点： 1. 思路：n! 和 a 可以分解为 1000以内的质因数的组合， 1. 例如 (6!, 10 )= 2 3 5 2 2 3 2 1, 2 5, 而 2 和 5在 6! 的质因数中分别出现的次数是 4和 1 ，取其小的，则得到 1。故 6! 只能被 10的 1次方整除。 2. 实现：getPrimeFac 得到1000内的质数，然后&nb...

2026年2月3日 10:05

整除问题题解：

P1284

回复 0 | 赞 0 | 浏览 139

num=list(map(int,input().split())) n=num[0] a=num[1] count=1 for i in range(1,n+1): count*=i k=0 i=0#记录最大的 while(a**i<count): if(count%(a**i)==0 and count%(a**(i+1))!=0): k+=i i+=1 print(k)

2026年2月1日 15:10

整除问题题解：丑陋的做法，分解阶乘和a的质因数为数组，然后做减法

P1284

回复 0 | 赞 3 | 浏览 184

#include<bits/stdc++.h> using namespace std; const int maxn = 1e3 +10; int prime[maxn] = {0}; void getPrime(){ for(int i = 2;i <= maxn;i++){ if(!prime[i]) prime[++prime[0]] = i; for(int ...

2025年8月9日 18:04

整除问题题解（求质因子解法）：

P1284

回复 0 | 赞 21 | 浏览 825

n!=1*2*3*...*n,所以n!的质因子就是1、2、3、...... 、n的质因子的集合 a^k=a*a*...*a，那么a^k的质因子的集合就是a的质因子集合乘k #include<bits/stdc++.h> using namespace std; // 线性素数筛 const int maxn = 1000 + 5; int prime[maxn]; void getPrime(){ memset(prime, 0, sizeof(prime)); for(int i = 2; i < maxn; i ++...

2025年3月9日 17:02

整除问题题解：

P1284

回复 0 | 赞 14 | 浏览 1.3k

#include <iostream> #include <cstring> using namespace std; const int maxm = 1000005; int p[maxm]; void ifsushu(){ memset(p, 0, sizeof(p)); // 初始化所有数为素数 for(int i = 2; i < maxm; i++){ &nb...

2025年1月16日 18:03

整除问题题解：

P1284

回复 0 | 赞 60 | 浏览 2.0k

#include<bits/stdc++.h> using namespace std; //质因子在本题中的作用要搞清楚，就是，如果a/b能整除，那么b的质因子一定是a的质因子的子集。 //若a=a1*a2*a3*...*an，那么a的质因子就是a1、a2、...、an的质因子的集合 //质因子中的质字体现了每个质因子的独特性，即如果b有k个质因子x， //那么a必须有大于等于k个质因子x才能保证a/b能整除 //再看本题，n!=1*2*3*...*n,所以n!的质因子就是1、2、3、、、n的质因子的集合 //a^k=a*a*...*a，那么a^k的质因...

1
2

题目整除问题

题解数量20

发布题解在线答疑

热门题解

1 详细题解（站在巨人的肩膀上）

2 整除问题题解：

3 整除问题题解（求质因子解法）：

4 整除问题题解：

5 整除问题题解：经典的阶乘质因数分解问题

6 整除问题题解：

7 大整数；将a拆分成若干个质因子之积，比较阶乘的 2 ~ n 中包含多少个对应的质因子，可得出来最多可以整除 a 的多少次方

8 数学问题之分解质因数

9 简单思路（素因数数组）

10 整除问题题解：用 map 对比