【No.19】蓝桥杯简单数论上|模运算|快速幂|GCD|LCM|刷题统计|RSA解密|核桃的数量(C++)

简单数论

模运算

• 定义：模运算为 a 除以 m 的余数，记为 a mod m，有 a mod m = a % m
• 模运算是大数运算中的常用操作。
• 如果一个数太大，无法直接输出，或者不需要直接输出，可以把它取模后，缩小数值再输出。
• Python 虽然能直接计算大数，不用担心数据溢出，但是大数乘法太耗时，所以也常用取模来缩小数值。
• 一个简单应用，判断奇偶：a%2==0，a 是偶数；a%2==1，a 是奇数

例题：刷题统计 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)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{ll a,b,n; cin >> a >> b >> n;    //先输入a,b,nll week = a * 5+b * 2;     //每周做题ll days = (n / week) * 7;  //目前的天数n %= week;             //剩下的做题数if(n <= a * 5)       //在周一到周五内days += n / a + (n % a ? 1 : 0);  //n/a计算整天数，还剩余的话+1else{                  //周六和周日//不是在前五天，先把这5天加上，总刷题数再减去这5天做的days += 5, n -= a * 5;//再判断n/b，现在n只能是0~2b-1，判断需不需要多加1天days += n / b + (n % b ? 1 : 0);}cout << days;return 0;
}

快速幂

幂运算 $a^n$，当 n 很大时，如果一个个乘，时间是 O(n) 的，速度很慢，此时可以用快速幂，在 O(logn) 的时间内算出来。
快速幂的一个解法：分治法，算 $a^2$，然后再算$(a^2{)}^2$ ，…，一直算到 $a^n$，代码也容易写。

• 标准的快速幂：用位运算实现。
• 基于位运算的快速幂，原理是倍增。

快速幂原理

以 $a^{11}$ 为例说明如何用倍增法做快速幂。
（1）幂次与二进制的关系。把 $a^{11}$ 分解成幂 $a^8$、$a^2$、$a^1$ 的乘积：$a^{11}=a^{8+2+1}=a^8\ast a^2\ast a^1$。其中$a^1$、$a^2$、$a^4$、$a^8$…的幂次都是 2 的倍数，所有的幂 $a^i$ 都是倍乘关系，逐级递推，代码： a *= a
（2）幂次用二进制分解。如何把 11 分解为 8+2+1？利用数的二进制的特征，n = $11_{10}$ = $1011_2$ = $2^3+2^1+2^0=8+2+1$ ，把 n 按二进制处理就可以。
（3）如何跳过那些没有的幂次？例如 1011 需要跳过 $a^4$。做个判断，用二进制的位运算实现：

• n & 1 ：取 n 的最后一位，并且判断这一位是否需要跳过。
• n >>= 1 ：把 n 右移一位，目的是把刚处理过的 n 的最后一位去掉。
  幂运算的结果往往很大，一般会先取模再输出。 根据取模的性质有：
  a^n mod m = (a mod m)^n mod m
  所以可以边做幂边取模

例题：快速幂 lanqiaoOJ 题号 1514

【题目描述】
给定 b, p, k，求(b^p) mod k。
其中 2≤b, p, k≤10^9。
【输入描述】
三个整数 b，p，k。
【输出描述】
输出(b^p) mod k。

题目解析

#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)     //取第一位，如果是1的话ans = (ans*a) % mod;   //取模，纳入到ans里面去a = a*a % mod;             //取模，a倍增n >>= 1;       //把这位去掉}return ans;
}
int main(){ll b, p, k;    cin >> b >> p >> k;cout << fastPow(b,p,k);return 0;
}

RSA解密

【题目描述】
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$ modn。
例如，当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，请问，原文是多少?

题目解析

(1)求p、q (两个质数 p、q，n=p·q)
先求n的素因子p和q。由于n只有p、q这2个因子，没有别的因子，所以p和q必然有一个小于$\sqrt{n}$，找到一个，另一个就知道了。
用暴力法求p、q，用i循环从2到$\sqrt{n}$一个个试。
若n除以i的余数是0，i就是因子。
循环次数是$n=\sqrt{1001733993063167141}$，
1000866621即十亿次计算。得到:p=891234941、q=1123984201

#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;
}

(2)求e (找到e 使得d·e 除(p-1)·(q-1)的余数为1
用到大数了。c++的64位long long不够用，虽然有 int128类型，但是有些编译器不支持。
还是用Python，下面代码打印出e=823816093931522017。
注意e有很多个，取最小的一个就行了。

#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);   //有很多e，求第一个就行了break;}}return 0;
}

(3)求X=$C^e$ mod n

#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));//打印结果:579706994112328949return 0;
}

GCD 定义、性质

最大公约数 Greatest Common Divisor(GCD)：
整数 a 和 b 的 GCD 是指能同时整除 a 和 b 的最大整数，记为 gcd(a, b)。由于-a 的因子和 a 的因子相同，因此 gcd(a, b) = gcd(|a|, |b|)。
编码时只关注正整数的最大公约数。
性质：

1. gcd(a, b) = gcd(a, a+b) = gcd(a, k·a+b)
2. gcd(ka, kb) = k·gcd(a, b)
3. 定义多个整数的最大公约数：gcd(a, b, c) = gcd(gcd(a, b), c)。
4. 若 gcd(a, b) = d，则 gcd(a/d, b/d) = 1，即 a/d 与 b/d 互素
5. gcd(a+cb, b) = gcd(a, b)

c++函数 std::__gcd()，可以返回负数，可以带多个参数。

#include <bits/stdc++.h>
using namespace std;
int main()
{cout << __gcd(15, 81) << "\n";    // 输出  3cout << __gcd(0, 44) << "\n";     // 输出  44cout << __gcd(0, 0) << "\n";      // 输出  0cout << __gcd(-6, -15) << "\n";   // 输出  -3cout << __gcd(-17,289) << "\n";   // 输出  -17cout << __gcd(17,-289) <<"\n";   // 输出  17return 0;
}

手写 GCD 代码

手写 gcd 函数，常用欧几里得算法。
辗转相除法求 gcd：
gcd(a, b) = gcd(b, a mod b) 
这是最常用的方法，极为高效。
设 a > b，辗转相除法的计算复杂度为$O(({\log }_{2}a{)}^3)$。

可输出负数，和库函数一样:

#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";    // 输出  3cout << gcd(0, 44) << "\n";     // 输出  44cout << gcd(0, 0) << "\n";      // 输出  0cout << gcd(-6, -15) << "\n";   // 输出  -3cout << gcd(-17,289) << "\n";   // 输出  -17cout << gcd(17,-289) << "\n";   // 输出  17return 0;
}
// 或者使用如下编码方式：
// int GCD(int a,int b)
// {
//     if(b==0)
//         return a;
//     return GCD(b,a%b);
// }

LCM

最小公倍数 LCM (the Least Common Multiple) 。
a 和 b 的最小公倍数 lcm(a,b),从算术基本定理推理得到。
算术基本定理：任何大于 1 的正整数 n 都可以唯一分解为有限个素数的乘积：
$n=p_1^{c_1}{p}_2^{c_2}{p}_3^{c_3}\dots p_m^{c_m}$​,其中$c_i$ 都是正整数，$p_i$​ 都是素数且从小到大。

推导 LCM：
设:$a=p_1^{c_1}{p}_2^{c_2}{p}_3^{c_3}\dots p_m^{c_m}$​​,$b=p_1^{f_1}{p}_2^{f_2}{p}_3^{f_3}\dots p_m^{f_m}$

那么：$gcd(a,b)=p_1^{min(c_1,f_1)}{p}_2^{min(c_2,f_2)}{p}_3^{min(c_3,f_3)}\dots p_m^{min(c_m,f_m)}$

$lcm(a,b)=p_1^{max(c_1,f_1)}{p}_2^{max(c_2,f_2)}{p}_3^{max(c_3,f_3)}\dots p_m^{max(c_m,f_m)}$

推出：$gcd(a,b)\ast lcm(a,b)=a\ast b$
即：
$lcm(a,b)=a\ast b/gcd(a,b)=a/gcd(a,b)\ast b$

lcm()手写代码

//c or c++
int lcm(int a, int b)
{    //需要的时候把int改成long longreturn a / gcd(a, b) * b;  //先做除法再做乘法，防止先做乘法溢出
}

核桃的数量 2013 年第四届省赛 lanqiaoOJ 题号 210

【题目描述】
小张是软件项目经理，他带领 3 个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：

1. 各组的核桃数量必须相同
2. 各组内必须能平分核桃（当然是不能打碎的）
3. 尽量提供满足 1, 2 条件的最小数量（节约闹革命嘛）
   【输入格式】
   输入三个正整数 a, b, c，表示每个组正在加班的人数，用空格分开
   （a,b,c< 30）
   【输出格式】
   输出一个正整数，表示每袋核桃的数量。

题目解析

简单题，答案就是三个数字的最小公倍数。

#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;
}