P1284 整除问题 - 题解

登录注册上岸

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

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

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

2024年9月4日 10:25

整除问题题解：

P1284

回复 0 | 赞 1 | 浏览 2.4k

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

2024年3月23日 20:46

下次还填非常简单

P1284

回复 0 | 赞 0 | 浏览 1.5k

#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 | 浏览 2.0k

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

思路：整数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.8k

#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 | 赞 5 | 浏览 11.0k

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

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

2021年1月17日 10:18

P1284

回复 0 | 赞 5 | 浏览 9.9k

思路： 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...

2020年4月17日 16:08

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

P1284

回复 0 | 赞 0 | 浏览 11.3k

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 = ...

1
2

题目整除问题

题解数量20

发布题解在线答疑

热门题解

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

2 整除问题题解：

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

4 整除问题题解：

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

6 整除问题题解：

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

8 数学问题之分解质因数

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

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