P1284 整除问题 - 题解

登录注册上岸

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

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

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

2025年3月9日 17:02

整除问题题解：

P1284

回复 0 | 赞 9 | 浏览 632

#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 | 赞 45 | 浏览 1.1k

#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的质因...

2024年9月4日 10:25

整除问题题解：

P1284

回复 0 | 赞 1 | 浏览 1.9k

#include<bits/stdc++.h> using namespace std; int cal_days(int year,int month,int day) { int days[12] = {31,28,31,30,31,30,31,31,30,31,30,31}; int sum=0; su...

2023年2月16日 14:41

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

P1284

回复 1 | 赞 69 | 浏览 5.7k

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

2024年3月23日 20:46

下次还填非常简单

P1284

回复 0 | 赞 0 | 浏览 1.1k

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

2023年7月29日 19:40

整除问题题解：

P1284

回复 0 | 赞 1 | 浏览 1.6k

这题也是看了别人的解析才明白的，理解之后我利用map进行计数。 #include <bits/stdc++.h> using namespace std; const int maxn=10005; int prime[maxn]; void getPrime(){ memset(prime,0,sizeof(...

2023年1月25日 16:46

先打表再算提供的因数个数

P1284

回复 0 | 赞 1 | 浏览 3.5k

#include <bits/stdc++.h> #include <unordered_map> using namespace std; typedef long long ll; const int N=1e4+7,INF = 0x3f3f3f3f;; typedef pair<int, int> PII; unordered_map<int, int>cnt1; unordered_map<int, int>cnt2; int n,m,a; // 点的数量 int prime[N],fla...

想想y总会怎么做

2022年2月26日 15:52

数学问题之分解质因数

P1284

回复 0 | 赞 6 | 浏览 7.7k

思路：整数a可以分解为若干质因数的成绩，如形式：a=p1^x1 p2^x2... 同理，n！也可以分解为如上的形式：n!=p1^y1 p2^y2....（p1,p2为质因数）则问题可以由a^k和n！的比较转换为两者质因数的比较。此时k的最大值即为两者质因数的幂次比值的最小值。细节：求质因数幂次的方法： void GetPrime(vector<int> &factor,int num) { for(int i=2;i*i<=num;i++)//统计所有小于sqrt(num)的素因...

2021年5月25日 21:00

大整数；将a拆分成若干个质因子之积，比较阶乘的 2 ~ n 中包含多

P1284

回复 0 | 赞 11 | 浏览 9.3k

#include<bits/stdc++.h> using namespace std; //得到数n的质因子及其个数 void getPrime(vector<int>& factors, int n){ for(int i=2; i*i<=n; i++){ while(n % i == 0){ factors[i]++; n /= i; if(n <= 1) return; } } if(n > 1) factors[n]++; } int main...

2021年1月29日 23:26

质因数分解

P1284

回复 0 | 赞 4 | 浏览 10.4k

#include<iostream> #include<math.h> using namespace std; /* 思路：将n!对于 2 3 4 .... n质因数分解将对应的质因数个数桶方式记录在p1 将a 质因数分解记录在p2 从2开始遍历如果每一项都保证p1[i]>p2[i]*k那么a^k一定可以整除开n! &nbs...

1
2

题目整除问题

题解数量13

发布题解在线答疑

热门题解

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

2 整除问题题解：

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

4 整除问题题解：

5 数学问题之分解质因数

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

7 简单思路

8 质因数分解

9 整除问题题解：

10 先打表再算提供的因数个数