黑龙江网站建设开发,个人简历网页html代码,网站开发企业,专业做数据的网站有哪些方面简单数论
模运算
定义#xff1a;模运算为 a 除以 m 的余数#xff0c;记为 a mod m#xff0c;有 a mod m a % m模运算是大数运算中的常用操作。如果一个数太大#xff0c;无法直接输出#xff0c;或者不需要直接输出#xff0c;可以把它取模后#xff0c;缩小数值再…简单数论
模运算
定义模运算为 a 除以 m 的余数记为 a mod m有 a mod m a % m模运算是大数运算中的常用操作。如果一个数太大无法直接输出或者不需要直接输出可以把它取模后缩小数值再输出。Python 虽然能直接计算大数不用担心数据溢出但是大数乘法太耗时所以也常用取模来缩小数值。一个简单应用判断奇偶a%20a 是偶数a%21a 是奇数
例题刷题统计 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 * 5b * 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^{821}a^{8}*a^{2}*a^{1} a11a821a8∗a2∗a1。其中 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 分解为 821利用数的二进制的特征n 1 1 10 11_{10} 1110 101 1 2 1011_{2} 10112 2 3 2 1 2 0 8 2 1 2^32^12^0821 232120821 把 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。 【输入描述】 三个整数 bpk。 【输出描述】 输出(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令np·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。 例如当p5q11d3时n55e27. 若加密数字24得 2 4 3 24^3 243 mod 55 19。解密数字19得 1 9 27 19^{27} 1927 mod 55 24。 现在你知道公钥中n1001733993063167141d212353同时你截获了别人发送的密文C20190324请问原文是多少?
题目解析
(1)求p、q (两个质数 p、qnp·q) 先求n的素因子p和q。由于n只有p、q这2个因子没有别的因子所以p和q必然有一个小于 n \sqrt{ n } n 找到一个另一个就知道了。 用暴力法求p、q用i循环从2到 n \sqrt{ n } n 一个个试。 若n除以i的余数是0i就是因子。 循环次数是 n 1001733993063167141 n\sqrt{1001733993063167141 } n1001733993063167141 1000866621即十亿次计算。得到:p891234941、q1123984201
#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下面代码打印出e823816093931522017。 注意e有很多个取最小的一个就行了。
#include bits/stdc.h
using namespace std;
typedef __int128 ll;
void print(__int128 num)
{//递归调用实现从高位向低位输出if(num9)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(Cen));//打印结果:579706994112328949return 0;
}GCD 定义、性质
最大公约数 Greatest Common Divisor(GCD) 整数 a 和 b 的 GCD 是指能同时整除 a 和 b 的最大整数记为 gcd(a, b)。由于-a 的因子和 a 的因子相同因此 gcd(a, b) gcd(|a|, |b|)。 编码时只关注正整数的最大公约数。 性质
gcd(a, b) gcd(a, ab) gcd(a, k·ab)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(acb, 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)。
可输出负数和库函数一样:
#includebits/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(b0)
// 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 np_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}} np1c1p2c2p3c3…pmcm,其中 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 ap_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}} ap1c1p2c2p3c3…pmcm, b p 1 f 1 p 2 f 2 p 3 f 3 … p m f m bp_{1}^{f_{1}}p_{2}^{f_{2}}p_{3}^{f_{3}}\dots p_{m}^{f_{m}} bp1f1p2f2p3f3…pmfm
那么 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)a∗b 即 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)a∗b/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 条件的最小数量节约闹革命嘛 【输入格式】 输入三个正整数 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;
}
