ACM数论部分学习(持续更新)
2021/5/19 10:26:30
本文主要是介绍ACM数论部分学习(持续更新),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数论部分
自bilibili n多视频
https://www.bilibili.com/video/BV1Zf4y1r7qE?from=search&seid=9993155426548406857
以及https://oi-wiki.org/
学习
模运算
模运算
常用于结果对某数取模
(a+b)mod m = ((a mod m)+(b mod m)) mod m;
(a-b)mod m = ((a mod m)-(b mod m)) mod m;
(ab)mod m = ((a mod m)(b mod m)) mod m;
注意:除法取模需要用到逆元 与上述式子不符。
快速幂
an–>an/2*an/2
若n为偶数,直接进行,若n为奇数,返回an/2*an/2*a即可,因为Int类型除以二会向下整除。
参考代码:
递归形式代码: long long fastpower2(long long a,int n){ if(n==1) return a; long long temp = fastpower2(a,n/2); if(n%2==1) return temp*temp*a; else return temp*temp; } 非递归形式代码: long long fastpower1(long long a,int n){ long long ans=1; while(n){ if(n&1) ans*=a; a*=a; n>>=1; } return ans; }
位运算
汉字 | 符号 |
---|---|
与 | & |
或 | |
异或 | ^ |
非 | ~ |
一个数异或两次得原数
GCD最大公因数以及LCM最小公倍数
辗转相除:gcd(a,b)=gcd(b,a%b)
更相减损:gcd(a,b)=gcd(b,a-b);
LCM a与b的最小公倍数:a*b/gcd(a,b);
可重复贡献:gcd(a,b,c)=gcd(gcd(a,b),c); so LCM
gcd(a,0)=a; gcd(a,b)=gcd(a,-b);
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
进制转换
printf("%05o\n",35); //按八进制格式输出,保留5位高位补零
printf("%03d\n",35); //按十进制格式输出,保留3位高位补零
printf("%05x\n",35); //按十六进制格式输出,保留5位高位补零
十进制转任意进制:
void Convert(int i,int b) { if(i==0)//递归出口 { return; } a[cnt++]=i%b; Convert(i/b,b); }
任意进制转十进制:
int rToTen(string n,int r){ //将r进制转为10进制,n是该r进制的字符串表示 int len = n.length(); int ans = 0; int i = 0; while(i<len){ ans*=r; ans+=n[i]-'0'; i++; } return ans; }
这篇关于ACM数论部分学习(持续更新)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享