数论
知识点
- 模运算
- 快速幂
- 素数
- 质因子
- GCD/LCM
模运算
定义： 模运算是指计算一个整数除以另一个整数后得到的余数。在数学中，用符号“%”表示模运算，例如 a % b 就表示 a 除以 b 的余数。
模运算是大数运算中的常用操作。 如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后，缩小数值再输出。 Python 虽然能直接计算大数，不用担心数据溢出，但是大数乘法太耗时，所以也常用取模来缩小数值。
一个最简单应用，判断奇偶：a%2 == 0，a 是偶数；a%2 == 1，a 是奇数
快速幂
幂运算__，当 n 很大时，如果一个个地乘，时间是 O(n)的，速度很慢，此时可以用快速幂，在 O(logn)的时间内算出来。
快速幂的一个解法：分治法，算 ，然后再算，…，一直算到 ，代码也容易写。
标准的快速幂：用位运算实现。
基于位运算的快速幂，原理是倍增。
快速幂的原理：
以 为例说明如何用倍增法做快速幂。
- 幂次与二进制的关系。把 分解成幂 、 、 的乘积：= = × × 。其中 、、、…的幂次都是 2 的倍数，所有的幂 都是倍乘关系，逐级递推，代码： a *= a
- 幂次用二进制分解。如何把 11 分解为 8+2+1？利用数的二进制的特征，n = 1011 = ++ = 8+2+1，把 n 按二进制处理就可以。
- 如何跳过那些没有的幂次？例如 1011 需要跳过 。做个判断，用二进制的位运算实现： n & 1 取 n 的最后一位，并且判断这一位是否需要跳过。 n >>= 1 把 n 右移一位，目的是把刚处理过的 n 的最后一位去掉。 幂运算的结果往往很大，一般会先取模再输出。 根据取模的性质有： mod m = mod m
快速幂模板：
我们使用为例,来写一个快速幂的模板。
代码描述：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; //变量改用较大的long long
ll fastPow(ll a, ll n, ll mod){
ll ans = 1;
a %= mod; //重要，防止下面的ans*a越界
while(n) {
if(n & 1) ans = (ans*a) % mod; //取模
a = a*a % mod; //取模
n >>= 1;
}
return ans;
}
int main(){
ll b,p,k; cin>>b>>p>>k;
cout << fastPow(b,p,k);
return 0;
}
import java.util.Scanner;
public class Main {
static long fastPow(long a, long n, long mod) {
long ans = 1;
a %= mod; //重要，防止下面的ans*a越界
while (n > 0) {
if ((n & 1) == 1) {
ans = (ans * a) % mod; //取模
}
a = (a * a) % mod; //取模
n >>= 1;
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long b = sc.nextLong(), p = sc.nextLong(), k = sc.nextLong();
System.out.println(fastPow(b, p, k));
sc.close();
}
}
def fast_pow(a, n, mod):
ans = 1
a %= mod #重要，防止下面的ans*a越界
while n > 0:
if n & 1 == 1:
ans = (ans * a) % mod #取模
a = (a * a) % mod #取模
n >>= 1
return ans
b, p, k = map(int, input().split())
print(fast_pow(b, p, k))
※素数
素数定义：只能被 1 和自己整除的正整数。注：1 不是素数，最小素数是 2。
判断一个数 n 是不是素数：
当 n ≤ 1014 时，用试除法；
当n > 1014 时，试除法不够用，需要用高级算法，例如 Miller_Rabin 算法。
试除法：用内的所有数去试着除 n，如果都不能整除，就是素数。
优化：把缩小到 。证明：若 n = a×b，其中 ， ，如果 n 有个因子是 a，说明 n 不是素数，b 不用再试。
C++ 语言描述：
int is_prime(int n){
if(n<=1) return 0;
for(int i=2;i<=sqrt(n);i++)
if(n%i==0) return 0;
return 1;
}
试除法判断是不是素数的效率还是太低了，我们需要另一种方式来判断是不是素数。
素数筛法是一种常见的寻找素数的算法。具体来说，素数筛法通过对数列进行筛选，逐步剔除素数的倍数来找到素数。
基本思想：从 2 开始，将 2 的倍数标记为合数；然后再从下一个未标记过的数 3 开始，将 3 的倍数标记为合数；依次循环下去，直到筛选完所有小于某个给定数的正整数。
最终，剩下未被标记为合数的数字即为素数。由于这种算法在实现上使用了一个数组进行标记，因此也被称为“埃拉托斯特尼筛法”（Sieve of Eratosthenes）。
素数筛法的优点在于它只需要执行一次线性时间复杂度的操作，就可以快速找到小于给定数的所有素数。因此，在需要频繁进行素数判断的场合，素数筛法是一种非常高效的算法。
我们模拟一下埃氏筛法的实现原理：
初始数组{2、3，4，5，6，7，8，9，10，11，12，13，…，n}，操作步骤：
- 找到下一个未被标记的数 2，筛掉 2 的倍数，得{
2，3，4，5，6，7，8，9，10，11，12，13，…} - 找到下一个未被标记的数 3，筛掉 3 的倍数，得{
2，3，4，5，6，7，8，9，10，11，12，13，…} - 找到下一个未被标记的数 5，筛掉 5 的倍数，得{
2，3，4，5，6，7，8，9，10，11，12，13，…} 继续以上步骤，直到数组处理完。
那可以写出埃氏筛法的实现代码：
C++ 语言描述：
int primes[N],cnt;
bool bprime[N];
void getPrime(int n){
memset(bprime,false,sizeof(bprime));
bprime[0]=true;
bprime[1]=true;
for(int i=2;i<=n;i++){
if(!bprime[i]){
prime[cnt++]=i;
for(LL j=i*2;j<=n;j+=i)
bprime[j]=true;
}
}
}
但是埃氏筛法的缺点：例如 6 会被 3 整除，6 会被 2 整除，会被筛两次，所以我们再给出欧氏线性筛法，两种筛法掌握一种即可。
C++ 语言描述：
int primes[N],cnt;
bool bPrime[N];
void getPrimes(int n){
memset(bPrime,false,sizeof(bPrime));
for(int i=2;i<=n;i++){
if(!bPrime[i])
primes[cnt++]=i;
for(int j=0;j<cnt&&i*primes[j]<n;j++){
bPrime[i*primes[j]]=true;
if(i%primes[j]==0)
break;
}
}
}
质因子
唯一分解定理，又称为质因数分解定理，是指任何一个大于 1 的正整数，都可以表示为一些质数的乘积。并且，这些质数的指数可以不同，但是它们的组合却是唯一的。
换句话说，唯一分解定理告诉我们，一个大于 1 的正整数 n 可以表示为：
其中，p1、p2、…、pn 是不同的质数，k1、k2、…、kn 是正整数。如果一个正整数 n 除了 1 和本身以外不能被其它正整数整除，那么它就是质数，而且其质因子分解就是它本身。
分解质因子也可以用试除法。求 n 的质因子：
- 第一步，求最小质因子 p1。逐个检查从 2 到 的所有素数，如果它能整除 n，就是最小质因子。然后连续用 p1 除 n，目的是去掉 n 中的 p1，得到 n1。
- 第二步，再找 n1 的最小质因子。逐个检查从 p1 到 的所有素数。从 p1 开始试除，是因为 n1 没有比 p1 小的素因子，而且 n1 的因子也是 n 的因子。
- 继续以上步骤，直到找到所有质因子。
GCD/LCM
最大公约数GCD (Greatest Common Divisor)
整数 a 和 b 的 GCD 是指能同时整除 a 和 b 的最大整数，记为 gcd(a, b)。由于-a 的因子和 a 的因子相同，因此 gcd(a, b) = gcd(|a|, |b|)。编码时只关注正整数的最大公约数。
性质：
- gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b)
- gcd(ka, kb) = k·gcd(a, b)
- 定义多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)。
- 若 gcd(a, b) = d，则 gcd(a/d, b/d) = 1，即 a/d 与 b/d 互素。这个定理很重要。
- gcd(a+cb, b) = gcd(a, b)
我们在 C++中可以直接使用内置函数 gcd()，gcd() 可以对负数使用，符号与第一个参数有关。
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<__gcd(15, 81)<<"\n"; // 输出 3
cout<<__gcd(0, 44)<<"\n"; // 输出 44
cout<<__gcd(0, 0)<<"\n"; // 输出 0
cout<<__gcd(-6, -15)<<"\n"; // 输出 -3
cout<<__gcd(-17,289)<<"\n"; // 输出 -17
cout<<__gcd(17,-289)<<"\n"; // 输出 17
return 0;
}
Python 语言和 Java 语言是没有内置 gcd 函数的，我们应该如何编码？ 我们采用递归的方式手写辗转相除算法。gcd(a, b) = gcd(b, a mod b)
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){ return b? gcd(b, a%b):a; }
int main(){
cout<<gcd(15, 81)<<"\n"; // 输出 3
cout<<gcd(0, 44)<<"\n"; // 输出 44
cout<<gcd(0, 0)<<"\n"; // 输出 0
cout<<gcd(-6, -15)<<"\n"; // 输出 -3
cout<<gcd(-17,289)<<"\n"; // 输出 -17
cout<<gcd(17,-289)<<"\n"; // 输出 17
return 0;
}
如果你觉得三目运算符不太容易理解的话，笔者在这里给大家写一个展开的版本：
C++ 语言描述：
int GCD(int a,int b)
{
if(b==0)
return a;
return GCD(b,a%b);
}
最小公倍数 LCM（the Least Common Multiple）
a 和 b 的最小公倍数 lcm(a, b)，从算术基本定理推理得到。 唯一需要注意的是尽量不要写 ，而要改为 ，否则可能会导致乘法溢出，那我们就可以写出 lcm 的函数。
int lcm(int a, int b){ //需要的时候把int改成long long
return a / gcd(a, b) * b; //先做除法再做乘法，防止先做乘法溢出
}
Practice
刷题统计
2022 年第十三届省赛，lanqiaoOJ 题号 2098
【问题描述】 小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？
【输入格式】 输入一行包含三个整数 a, b 和 n。
【输出格式】 输出一个整数代表天数。
【评测用例规模与约定】 对于 50%的评测用例，1 ≤ a, b, n ≤ 10^6；对于 100%的评测用例，1 ≤ a, b, n ≤ 10^18。
解题思路： 求余数的简单题，利用求余，把计算复杂度降为 O(1)。
这道题比较简单我们可以很容易的写出程序。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll a,b,n; cin>>a>>b>>n;
ll week = a*5+b*2; //每周做题
ll days = (n/week)*7; //周数
n %= week; //剩下的做题数
if(n<=a*5) days += n/a+(n%a?1:0); //在周一到周五内
else{ //周六和周日
days += 5, n -= a*5;
days += n/b+(n%b?1:0);
}
cout<<days;
return 0;
}
快速幂(模板题)
lanqiaoOJ 题号 1514
【题目描述】给定 b, p, k，求(b^p) mod k。其中 2≤b, p, k≤10^9。
【输入描述】三个整数 b，p，k。
【输出描述】输出(b^p) mod k。
解题思路：
这个题目是快速幂的模板题，我可以按照题意套用快速幂的模板即可。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; //变量改用较大的long long
ll fastPow(ll a, ll n, ll mod){
ll ans = 1;
a %= mod; //重要，防止下面的ans*a越界
while(n) {
if(n & 1) ans = (ans*a) % mod; //取模
a = a*a % mod; //取模
n >>= 1;
}
return ans;
}
int main(){
ll b,p,k; cin>>b>>p>>k;
cout << fastPow(b,p,k);
return 0;
}
RSA 解密
2019 年第十届省赛，填空题，lanqiaoOJ 题号 603
【题目描述】
RSA 是一种经典的加密算法。它的基本加密过程如下。 首先生成两个质数 p、q，令 n=p⋅q，设 d 与(p−1)⋅(q−1) 互质，则可找到 e 使得 d⋅e 除(p−1)⋅(q−1) 的余数为 1。 n、d、e 组成了私钥，n、d 组成了公钥。 当使用公钥加密一个整数 X 时（小于 n），计算 C = X^d mod n，则 C 是加密后的密文。 当收到密文 C 时，可使用私钥解开，计算公式为 X = C^e mod n。 例如，当 p=5，q=11,d=3 时，n=55，e=27。 若加密数字 24，得 24^3 mod 55=19。解密数字 19，得 19^27 mod 55=24。 现在你知道公钥中 n = 1001733993063167141, d = 212353，同时你截获了别人发送的密文 C = 20190324，请问，原文是多少？
解题思路:
- 求 p、q （两个质数 p、q， n=p⋅q ） 先求 n 的素因子 p 和 q。由于 n 只有这 2 个因子，没有别的因子，所以 p 和 q 必然有一个小于，找到一个，另一个就知道了。用暴力法求 p、q，用 i 循环从 2 到 一个个试。若 n 除以 i 的余数是 0，i 就是因子。
循环次数是 ，即十亿次计算。
得到：p = 891234941、q = 1123984201。 这个步骤的代码如下:
C++ 语言描述：
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int main(){
ll n = 1001733993063167141;
ll k = sqrt(n);
for(ll i=2;i<=k;i++)
if(n % i == 0) cout<<i<<" "<<n/i;
return 0;
}
- 求 e（找到 e 使得 d⋅e 除(p−1)⋅(q−1) 的余数为 1 ） 用到大数了。c++的 64 位 long long 不够用，但有_int128 类型下面代码打印出 e = 823816093931522017。
注意 e 有很多个，取最小的一个就行了。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
void print(__int128 num)
{//递归调用，实现从高位向低位输出
if(num>9)
print(num/10);
putchar(num%10+'0');
}
int main(){
ll n = 1001733993063167141;
ll d = 212353;
ll p = 891234941;
ll q = 1123984201;
ll tmp = (p - 1) * (q - 1);
print(tmp);
puts("");
for(ll i=2; i<=n; i++){
ll now = i * tmp + 1;
if(now % d == 0){
ll t=now/d;
print(t);
break; //有很多e，求第一个就行了
}
}
return 0;
}
- 求 X = C^e mod n ，这一步骤考了快速幂。 C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
void print(__int128 num)
{//递归调用，实现从高位向低位输出
if(num>9)
print(num/10);
putchar(num%10+'0');
}
ll fastPow(ll a, ll b, ll mod){
ll ans = 1;
while(b){
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main(){
ll n = 1001733993063167141;
ll e = 823816093931522017;
ll C = 20190324;
print( fastPow(C, e, n)); //打印结果：579706994112328949
return 0;
}
核桃的数量
2013 年第四届省赛 lanqiaoOJ 题号 210
【题目描述】小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是： 1.各组的核桃数量必须相同 2.各组内必须能平分核桃（当然是不能打碎的） 3.尽量提供满足 1, 2 条件的最小数量（节约闹革命嘛）。
【输入格式】输入三个正整数 a, b, c，表示每个组正在加班的人数，用空格分开（a,b,c< 30） 。
【输出格式】输出一个正整数，表示每袋核桃的数量。
解题思路: 简单题，答案就是三个数字的最小公倍数。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
int lcm(int a, int b){ return a / __gcd(a, b) * b;}
int main(){
int a,b,c; cin>>a>>b>>c;
int k = lcm(a,b);
cout<<lcm(k,c)<<endl;
return 0;
}
Hankson 的趣味题
lanqiaoOJ 题号 520
【题目描述】在课堂上，老师讲解了如何求两个正整数 c1 和 c2 的最大公约数和最小公倍数。Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数 a0,a1,b0,b1，设某未知正整数 x 满足：
- x 和 a0 的最大公约数是 a1
- x 和 b0 的最小公倍数是 b1 Hankson 的“逆问题”就是求出满足条件的正整数 x。但稍加思索之后，他发现这样的 x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的 x 的个数。请你帮助他编程求解这个问题。
【输入格式】输入第一行为一个正整数 n，表示有 n 组输入数据。 接下来的 n 行每行一组输入数据，为四个正整数 a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证 a0 能被 a1 整除，b1 能被 b0 整除。 数据规模：对于 100%的数据，保证有 1≤a0，a1，b0，b1≤2,000,000,000 且 n≤2000。 【输出格式】输出共 n 行。每组输入数据的输出结果占一行，为一个整数。对于每组数据： 若不存在这样的 x，请输出 0；若存在这样的 x，请输出满足条件的 x 的个数。
解题思路:
若 x 是 b1 的因子，有 x*y = b1，y 也可能是答案。 只需要在范围 x≤sqrt(b1)内查询，同时判断 y 就行了。 但还是超时，因为 gcd 计算也要花时间，加上一个优化：if(b1%x==0)，表示 b1 是 x 的公倍数,即可通过。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
int lcm(int a, int b){ return a / __gcd(a, b) * b;}
int main() {
int n; scanf("%d",&n);
while(n--) {
int a0,a1,b0,b1;
cin >>a0>>a1>>b0>>b1;
int ans=0;
for(int x=1;x <= sqrt(b1);x++){
if(b1%x == 0){ //优化
if(__gcd(x,a0)==a1 && lcm(x,b0)==b1) ans++;
int y = b1/x; //另外一个因子
if(x==y) continue;
if(__gcd(y,a0)==a1 && lcm(y,b0)==b1) ans++;
}
}
cout << ans <<endl;
}
return 0;
}
寻找整数
2022 年第十三届省赛，填空题，lanqiaoOJ 题号 2131
【题目描述】有一个不超过 1017 的正整数 n，知道这个数除以 2 至 49 后的余数如下表所示，求这个正整数最小是多少。
解题思路:
从表格的第一个数 2 开始，逐个增加后面的数，找满足条件的 n。
- 满足第一个条件，除以 2 余 1 的数有：3、5、7、9、…此时步长 k = 2。
- 继续满足第二个条件，除以 3 余 2 的数，只能从上一步骤的 3、5、7、9、…中找，有 5、11、17、… 此时步长 k = 6，为什么 k = 6？ 实际上是 LCM：k = lcm(2, 3) = 6
- 继续满足第三个条件，除以 4 余 1 的数，只能从 5、11、17、…中找，有 5、17、29、…此时步长 k = lcm(2, 3, 4) = 12。
- 继续满足第四个条件，….
逐个检查表格，直到满足表格中所有的条件。 计算量极小，只需要对表格中的 2 ~ 49 做 48 次 LCM 即可。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
const int N = 50;
int mod[N] = {0,0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46};
int main() {
long long ans = 2 + mod[2];
long long k = 2; //从第一个数的步长开始
for (int i = 3; i < N; i++) {
while (true) {
if (ans % i == mod[i]) { //ans是满足前i个数的解
k = k / __gcd(k, (long long)i) * i; //连续做LCM
break;
} else {
ans += k; //累加新的步长
}
}
}
cout << ans << endl;
return 0;
}
最大最小公倍数
lanqiaoOJ 题号 1510
【题目描述】已知一个正整数 n，问从 1~N 中任选出三个数，他们的最小公倍数最大可以为多少。
【输入描述】一个正整数 N。
【输出描述】一个整数表示答案。
解题思路: 贪心，从大的数开始选。不过，简单地把 N 里面最大的三个数相乘，N*(N-1)*(N-2)，并不正确，需要分析多种情况。
最小的公倍数是三个数的质因数相乘，如果有几个质因数相同，则比较两数中哪个数的质因数的个数较多。例如 6、7、8 的最小公倍数，先分解因子：6=2×3，7=7×1，8=2×2×2，它们的最小公倍数是 3×7×2×2×2。
大于 1 的两个相邻整数互质，它们没有公共的质因数。如果题目是任选二个数，最大的最小公倍数是 N*(N-1)。
对于连续的三个整数，分两种情况：
- N 是奇数。N、N-1、N-2 是奇偶奇，结论是这三个数两两互质，三个数的乘积就是最大的最小公倍数。三个数两两互质，也就是说任意一个质数，只在 N、N-1、N-2 中出现一次。逐个分析质数： 质因数 2，只在 N-1 中出现。 质因数 3，如果在 N 中出现（设 N = 3a），就不会在 N-1 中出现（这要求 N-1 = 3b，无解），也不会在 N-2 中出现（这要求 N-2 = 3b，无解）。 推广到任何一个质数 k，都只会在 N、N-1、N-2 中出现一次，所以三个数互质。
- N 是偶数。 如果 N 为偶数，那么 N 与 N-2 最大公约数为 2，所以我们要找下一个质数，此时需要考虑 N 与 N-3 的关系： 如果 N 能被 3 整除，则 N-3 也能被 3 整除，此时 N 与 N-3 不互质，但是 N-1 与 N-3 必然互质（N-1、N-3 都为奇数），所以 N-1、 N-2、N-3 如果 N 不能被 3 整除，则 N-3 也不能被 3 整除，此时 N 与 N-3 互质，所以选择 N、N-1、N-3 。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
int main() {
long long n, ans;
cin >> n;
if(n <= 2) ans = n;
else if(n % 2) ans = n * (n - 1) * (n - 2); //n是奇数
else { //n是偶数
if(n%3) ans = n * (n-1) * (n-3); //n没有因数3
else ans = (n-1) * (n-2) * (n-3); //n有因数3
}
cout << ans;
return 0;
}
质数
【题目描述】给定一个正整数 N，请你输出 N 以内（不包含 N）的质数以及质数的个数。
【输入描述】一个正整数 N，n<1000。
【输出描述】两行，第 1 行包含若干个素数，从小到大输出，用空格分开。第 2 行一个整数，表示素数个数。
解题思路: 直接套用筛法的模板即可,其中: bprime[i]记录数 i 的状态，若 bprime [i]=1，表示它被筛掉，不是素数。 用 primes[]存放素数，prime[0]是第一个素数 2。 Cnt 是素数个数计数。
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int primes[N],cnt;
bool bprime[N]; //true表示被筛掉，不是素数
void getPrimes(int n){ //埃氏筛，计算[2, n]内的素数
memset(bprime,false,sizeof(bprime));
bprime[0]=true;
bprime[1]=true;
for(int i=2;i<=n;i++){
if(!bprime[i]){
primes[cnt++]=i;
for(int j=i*2;j<=n;j+=i)
bprime[j]=true;
}
}
}
int main(){
int n;
cin >>n;
getPrimes(n-1);
for(int i=0;i<cnt;i++) cout << primes[i]<<" ";
cout << endl;
cout << cnt;
}
分解质因数
lanqiaoOJ 题号 1559
【题目描述】求出区间[a,b]中所有整数的质因数分解。
【输入描述】输入一行，包含 2 个整数 a，b。2≤a≤b≤10000。
【输出描述】每行输出一个数的分解，形如 k=a1×a2×a3×…，k 从小到大，a 从小到大。
解题思路: 这是一道求质因子的模板题目,我们按照我们求质因子那部分知识即可写出代码.
C++ 语言描述：
#include<bits/stdc++.h>
using namespace std;
int p[20]; //p[]记录因子，p[1]是最小因子。一个int数的质因子最多有10几个
int c[40]; //c[i]记录第i个因子的个数。一个因子的个数最多有30几个
int factor(int n){
int m = 0;
for(int i = 2; i <= sqrt(n); i++)
if(n%i == 0){
p[++m] = i, c[m] = 0;
while(n%i == 0) //把n中重复的因子去掉
n/=i, c[m]++;
}
if(n>1) //没有被除尽，是素数
p[++m] = n, c[m] = 1;
return m; //共m个因子
}
int main(){
int a,b; cin>>a>>b;
for(int i=a;i<=b;i++){
int m = factor(i);
cout<<i<<"=";
for(int j=1;j<=m;j++){ //第j个因子
for(int k=1;k<=c[j];k++){ //第j个因子的个数
cout <<p[j];
if(k<c[j]) cout <<"*";
}
if(j<m) cout <<"*";
}
cout<<endl;
}
return 0;
}
质因数个数
【问题描述】
给定正整数 nn, 请问有多少个质数是 nn 的约数。
【输入格式】
输入的第一行包含一个整数 nn 。
【输出格式】
输出一个整数, 表示 nn 的质数约数个数。
【样例输入】
396
【样例输出】
3
解题思路:
直接对数字 n 进行质因数分解即可。 i 从 2 开始枚举判断是否为 n 的因子：如果 i 是因子，则把 n 不断除以 i 直到无法整除为止。最终如果 _n _!=1 ，说明在最后的 n 为质数，此时答案加 1。
C++ 语言描述：
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
int ans = 0;
int i = 2;
while (i * i <= n) {
if (n % i == 0) {
ans++;
while (n % i == 0) {
n /= i;
}
}
i++;
}
if (n != 1) {
ans++;
}
cout << ans << endl;
return 0;
}
也可以使用大数素数分解——Pollard_rho 算法：这是经典的大数素数分解算法模板，此处不展开赘述，可参考：
- Miller-Rabin 素性测试：https://blog.csdn.net/weixin_43914593/article/details/107290663(https://blog.csdn.net/weixin_43914593/article/details/107290663%5D)
- Pollard_rho 大数素数分解：https://blog.csdn.net/weixin_43914593/article/details/107345370(https://blog.csdn.net/weixin_43914593/article/details/107345370%5D)
数数
【问题描述】
任何一个大于 1 的正整数都能被分解为若干个质数相乘, 比如 28=2×2×728=2×2×7 被分解为了三个质数相乘。请问在区间 [2333333, 23333333] 中有多少个正整数 可以被分解为 12 个质数相乘?
**答案提交：**这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得
解题思路: 我们需要判断的数字数量大概有 的级别，如果按照朴素的分别质因数的方法，判断每个数最坏的时间复杂度基本是 级别，虽然是填空题，但是这个复杂度想跑出答案也是挺困难的。所以我们需要考虑优化，这里我们需要运用到一个性质：对于一个正整数 ，它最多只包含一个大于 的质因子。
这也非常好证明，如果存在两个及以上，那么相乘的值肯定大于了，就不可能都是 的质因子。这样我们判断每个数的复杂度就能降到 ，这个复杂度是我们可接受的。最终算出答案为:25606
C++ 语言描述：
public class Main {
public static void main(String[] args) {
int res=0;
for (int i = 2333333; i <=23333333; i++) {
int s=i;
int c=0;
for (int j = 2; j <=s/j; j++) {
while (s%j==0){
c++;
s/=j;
}
}
if (s>1) c++;
if (c==12) res++;
}
System.out.println(res);
}
}
最小质因子之和(Easy Version)
题目描述
定义 F(i) 表示整数 i 的最小质因子。现给定一个正整数 N，请你求出 。 输入描述
第 1 行为一个整数 T，表示测试数据数量。
接下来的 TT 行每行包含一个正整数 N。
1≤T≤10^6 1≤T≤10^6， 输出描述
输出共 T 行，每行包含一个整数，表示答案。
解题思路:
模板题
C++ 语言描述：
#include <stdio.h>
#define N 3000010
int primes[N],cnt=0;
long long f[N];
int np[N];
void get_primes(int n) {
for(int i=2; i<=n; i++) {
if(!np[i]) {
primes[cnt++]=i;
f[i]=i;
}
for(int j=0; primes[j]<=n/i; j++) {
np[primes[j]*i]=1;
f[primes[j]*i]=primes[j];
if(i%primes[j]==0) {
break;
}
}
}
}
int main() {
get_primes(N-1);
for(int i=2; i<N; i++) {
f[i]+=f[i-1];
}
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
printf("%lld\n",f[n]);
}
return 0;
}
最大体积
【题目描述】
每个物品有一定的体积（废话），不同的物品组合，装入背包会战用一定的总体积。
假如每个物品有无限件可用，那么有些体积是永远也装不出来的。为了尽量装满背包，附中的 OIER 想要研究一下物品不能装出的最大体积。
题目保证有解，如果是有限解，保证不超过 2×10^9，如果是无限解，则输出 0。 输入描述
第 11 行一个整数 n（n≤10），表示物品的件数。 第 2 行到 N+1 行: 每件物品的体积 (1∼500)。 输出描述
一个整数 ans，表示不能用这些物品得到的最大体积。
解题思路:
利用贝祖定理判断 n 个数是否最大公因数为 1，如果为 1 就用 dp 来获取不能装到的最大体积， 反之就代表有无限大的最大体积，输出 0。关于 dp，外循环是不同物品的体积，内循环是可能达到的总体积。 这里体积上限用 100000，因为体积太大了就算不出来。dp[j]=1 代表体积为 j 可以达到， dp[j]=0 则代表体积为 j 无法达到，转移方程为 if(dp[j-num[i]]=1) dp[j]=1 转移方程的意思是如果不放 num[i]都可以取到体积，那么加上 num[i]就一定能取到 初始状态 dp[0]=1 不放任何物品，体积就是 0
C++ 语言描述：
#include<iostream>
using namespace std;
#define MAX_NUM 100000
int n;
int num[505]; //保存物品的体积
int dp[MAX_NUM]; //保存物品能组成的所有体积
int gcd(int a,int b) //求两个数的最大公约数
{
if (a % b == 0)
return b;
else
return gcd(b, a % b);
}
int Bezout() //裴蜀定理求所有数的最大公约数
{
int temp = num[0];
for (int i = 1; i < n; i++)
{
temp = gcd(temp, num[i]);
}
return temp;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> num[i];
if (Bezout() == 1) //如果所有数的最大公约数为1,则有解，否则为无限解
{
dp[0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = num[i]; j <= MAX_NUM; j++)
{
if (dp[j - num[i]] == 1) //i=0时，j为num[0]的倍数；
//接下来，j为 num[i]中物品体积值组合的结果
dp[j] = 1;
}
}
for (int i = MAX_NUM; i >= 0; i--) //逆序遍历所有的体积结果，将第一个不能组合的数输出后结束
{
if (!dp[i])
{
cout<<i;
return 0;
}
}
}
cout<<"0"; //无限解
return 0;
}
比例简化
【问题描述】
在社交媒体上，经常会看到针对某一个观点同意与否的民意调查以及结果。例如，对某一观点表示支持的有 1498 人，反对的有 902 人，那么赞同与反对的比例可以简单的记为 1498:902。
不过，如果把调查结果就以这种方式呈现出来，大多数人肯定不会满意。因为这个比例的数值太大，难以一眼看出它们的关系。对于上面这个例子，如果把比例记为 5:3，虽然与真实结果有一定的误差，但依然能够较为准确地反映调查结果，同时也显得比较直观。
现给出支持人数 A，反对人数 B，以及一个上限 L，请你将 A 比 B 化简为 A′ 比 B′，要求在 A′和 B′ 均不大于 L 且 A′和 B′互质（两个整数的最大公约数是 1）的前提下，A′/B′≥A/B 且 A′/B′−A/B 的值尽可能小。
【输入描述】
输入共一行，包含三个整数 A，B，L，每两个整数之间用一个空格隔开，分别表示支持人数、反对人数以及上限。
其中，1≤A≤106，1≤B≤106，1≤L≤100，A/B≤L。
【输出描述】
输出共一行，包含两个整数 A′，B′，中间用一个空格隔开，表示化简后的比例。
解题思路:
通过先判断 A 和 B 的大小来优化循环次数
C++ 语言描述：
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
int main() {
int a, b, l;
cin >> a >> b >> l;
int A = 0, B = 0;
double minVal = 1e6;
if (a >= b) {
for (int i = 1; i <= l; i++) {
for (int j = 1; j <= i; j++) {
if (gcd(i, j) == 1 && static_cast<double>(i) / j >= static_cast<double>(a) / b) {
double diff = static_cast<double>(i) / j - static_cast<double>(a) / b;
if (diff < minVal) {
minVal = diff;
A = i;
B = j;
}
}
}
}
} else {
for (int i = 1; i <= l; i++) {
for (int j = i; j <= l; j++) {
if (gcd(i, j) == 1 && static_cast<double>(i) / j >= static_cast<double>(a) / b) {
double diff = static_cast<double>(i) / j - static_cast<double>(a) / b;
if (diff < minVal) {
minVal = diff;
A = i;
B = j;
}
}
}
}
}
cout << A << " " << B << endl;
return 0;
}
