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

本文主要是介绍【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 a^n an,当 n 很大时,如果一个个乘,时间是 O(n) 的,速度很慢,此时可以用快速幂,在 O(logn) 的时间内算出来。
快速幂的一个解法:分治法,算 a 2 a^2 a2,然后再算 ( a 2 ) 2 (a^2)^2 (a2)2 ,…,一直算到 a n a^n an,代码也容易写。

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

以  a 11 a^{11} a11 为例说明如何用倍增法做快速幂。
(1)幂次与二进制的关系。把 a 11 a^{11} a11 分解成幂  a 8 a^{8} a8 a 2 a^{2} a2 a 1 a^{1} a1 的乘积: a 11 = a 8 + 2 + 1 = a 8 ∗ a 2 ∗ a 1 a^{11}=a^{8+2+1}=a^{8}*a^{2}*a^{1} a11=a8+2+1=a8a2a1。其中 a 1 a^{1} a1 a 2 a^{2} a2 a 4 a^{4} a4 a 8 a^{8} a8…的幂次都是 2 的倍数,所有的幂  a i a^{i} ai 都是倍乘关系,逐级递推,代码: a *= a
(2)幂次用二进制分解。如何把 11 分解为 8+2+1?利用数的二进制的特征,n = 1 1 10 11_{10} 1110 = 101 1 2 1011_{2} 10112 = 2 3 + 2 1 + 2 0 = 8 + 2 + 1 2^3+2^1+2^0=8+2+1 23+21+20=8+2+1 ,把 n 按二进制处理就可以。
(3)如何跳过那些没有的幂次?例如 1011 需要跳过  a 4 a^4 a4。做个判断,用二进制的位运算实现:

  • 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 X^d Xd mod n,则C是加密后的密文。
当收到密文C时,可使用私钥解开,计算公式为X= C e C^e Ce modn。
例如,当p=5,q=11,d=3时,n=55,e=27.
若加密数字24,得 2 4 3 24^3 243 mod 55 = 19。解密数字19,得 1 9 27 19^{27} 1927 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必然有一个小于 n \sqrt{ n } n ,找到一个,另一个就知道了。
用暴力法求p、q,用i循环从2到 n \sqrt{ n } n 一个个试。
若n除以i的余数是0,i就是因子。
循环次数是 n = 1001733993063167141 n=\sqrt{1001733993063167141 } n=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 C^e Ce 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 ) O((\log_{2}a)^3) O((log2a)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 … p m c m n=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}} n=p1c1p2c2p3c3pmcm​,其中 c i c_{i} ci 都是正整数, p i p_{i} pi​ 都是素数且从小到大。

推导 LCM:
设: a = p 1 c 1 p 2 c 2 p 3 c 3 … p m c m a=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}} a=p1c1p2c2p3c3pmcm​​, b = p 1 f 1 p 2 f 2 p 3 f 3 … p m f m b=p_{1}^{f_{1}}p_{2}^{f_{2}}p_{3}^{f_{3}}\dots p_{m}^{f_{m}} b=p1f1p2f2p3f3pmfm

那么: g c d ( a , b ) = p 1 m i n ( c 1 , f 1 ) p 2 m i n ( c 2 , f 2 ) p 3 m i n ( c 3 , f 3 ) … p m m i n ( c 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})} gcd(a,b)=p1min(c1,f1)p2min(c2,f2)p3min(c3,f3)pmmin(cm,fm)

l c m ( a , b ) = p 1 m a x ( c 1 , f 1 ) p 2 m a x ( c 2 , f 2 ) p 3 m a x ( c 3 , f 3 ) … p m m a x ( 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})} lcm(a,b)=p1max(c1,f1)p2max(c2,f2)p3max(c3,f3)pmmax(cm,fm)

推出: g c d ( a , b ) ∗ l c m ( a , b ) = a ∗ b gcd(a,b)*lcm(a,b) = a*b gcd(a,b)lcm(a,b)=ab
即:
l c m ( a , b ) = a ∗ b / g c d ( a , b ) = a / g c d ( a , b ) ∗ b lcm(a,b)=a∗b/gcd(a,b)=a/gcd(a,b)∗b lcm(a,b)=ab/gcd(a,b)=a/gcd(a,b)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;
}

这篇关于【No.19】蓝桥杯简单数论上|模运算|快速幂|GCD|LCM|刷题统计|RSA解密|核桃的数量(C++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/851703

相关文章

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

Java中使用Hutool进行AES加密解密的方法举例

《Java中使用Hutool进行AES加密解密的方法举例》AES是一种对称加密,所谓对称加密就是加密与解密使用的秘钥是一个,下面:本文主要介绍Java中使用Hutool进行AES加密解密的相关资料... 目录前言一、Hutool简介与引入1.1 Hutool简介1.2 引入Hutool二、AES加密解密基础

Mysql如何将数据按照年月分组的统计

《Mysql如何将数据按照年月分组的统计》:本文主要介绍Mysql如何将数据按照年月分组的统计方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql将数据按照年月分组的统计要的效果方案总结Mysql将数据按照年月分组的统计要的效果方案① 使用 DA

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下:

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

Java调用C++动态库超详细步骤讲解(附源码)

《Java调用C++动态库超详细步骤讲解(附源码)》C语言因其高效和接近硬件的特性,时常会被用在性能要求较高或者需要直接操作硬件的场合,:本文主要介绍Java调用C++动态库的相关资料,文中通过代... 目录一、直接调用C++库第一步:动态库生成(vs2017+qt5.12.10)第二步:Java调用C++

使用Python开发一个简单的本地图片服务器

《使用Python开发一个简单的本地图片服务器》本文介绍了如何结合wxPython构建的图形用户界面GUI和Python内建的Web服务器功能,在本地网络中搭建一个私人的,即开即用的网页相册,文中的示... 目录项目目标核心技术栈代码深度解析完整代码工作流程主要功能与优势潜在改进与思考运行结果总结你是否曾经