GCD LCM 素数 快速幂
2018-07-23 05:31:05来源:博客园 阅读 ()
1.********** GCD(最大公约数)
代码实现(复杂度为O(logn))
int gcd ( int a, int b){
return b ? gcd ( b , a % b ) : a ;
}
2.*********** LCM(最小公倍数)
lcm(a,b) = a * b / gcd(a,b);
3.******** 素数
代码实现(复杂度为O(logn))
函数isprime返回值中 值为1代表素数,值为0代表非素数
int isprime(int a){
if(a==1) return 0;
for(int i=2;i<=sqrt(a);i++){
if(a%i==0) return 0;
}
return 1;
}
4.********素数打表
代码实现(复杂度为O(nloglogn))
数组nisprime中 值为0代表素数,值为1代表非素数
const int MAXN = (int)(打表范围);
int nisprime[MAXN];
void init() {
nisprime[1] = 1;
for(int i = 2; i < MAXN; i++) {
if(!nisprime[i])
for(long long j = i * i; j < MAXN; j += i) {
nisprime[j] = 1;
}
}
}
//判断输入数值i是否为素数,只需判断nisprime[i]的值即可
5.******** 快速幂
代码实现(复杂度为O(logn))
#define ll long long
ll poww(ll a,ll b,ll c){
ll ant=1;
while(b){
if(b&1) ant = (ant * a ) % c;
a=a*a%c;
b>>=1;
}
return ant;
}
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 清北学堂day3 2019-11-04
- Prime Time UVA - 10200(精度处理,素数判定) 2019-08-16
- GCD&&素筛&&快速幂 --A - 2019-08-16
- [ bzoj2820] YY的GCD 2019-06-13
- 简单的素数问题(C++) 2019-01-23
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash