P1284 整除问题 - 题解

登录注册上岸

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

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

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

2024年9月4日 10:25

整除问题题解：

P1284

回复 0 | 赞 0 | 浏览 891

#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 | 赞 9 | 浏览 4.4k

此题解是对前面题解的详细解答。（是看了各位大神的代码才知道怎么写的，自己想我大概是想不出来的，感谢各位佬）题干：给定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 | 浏览 560

#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.1k

这题也是看了别人的解析才明白的，理解之后我利用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.0k

#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 | 赞 1 | 浏览 7.0k

思路：整数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 | 赞 5 | 浏览 8.9k

#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 | 赞 1 | 浏览 9.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...

2021年1月26日 17:35

简单思路（素因数数组）

P1284

回复 0 | 赞 0 | 浏览 8.2k

具体思路如下：1. 求出n!的所有素因数，开一个数组p1，以值为下标保存个数。该题n为1000以内，开一个1000的数组就可以了。默认值都为0 2. 求出a的所有素因数，同样开一个数组p2，以值为下标保存个数。默认值都为0 3. 通过求得的素数数组把p1，p2数...

2021年1月17日 10:18

P1284

回复 0 | 赞 2 | 浏览 9.2k

思路： 1、对N!分解质因数，所以分别对1、2、3……N分解质因数，然后用一个数组下标记录该质因数的个数 2、对a分解质因数，然后计算相同质因数下，1步质因数个数除以2步质因数个数的最小值即为所求 #include <bits/stdc++.h> using namespace std; const int maxn = 1000; int prime[2][maxn]; void getPrime() { memset(prime, 0, sizeof(prime)); for (int i = 2; i...

1
2

题目整除问题

题解数量11

热门题解

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

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

3 简单思路

4 数学问题之分解质因数

5 整除问题题解：

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

7 质因数分解

8 下次还填非常简单

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

10 找的其他人的思路，比较简单，主要是java中bigInteger的应用