• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

数学部分笔记

模运算(mod/%)

算法竞赛中经常用到各种模运算。下面总结一下常用的,供大家自己复习。

什么是取模运算

在java和c/c++中

对于整数a,b,模运算:

1.求整数商3360 c=a/b;

2.计算模块: a % b=a-c * b例子:

9 % 4=9 - (9/4) * 4=1

9 %-4=9 - (9 /-4) *-4=1

-9 % 4=-9 - (-9/4) * 4=-1

-9 %-4=-9 - (-9 /-4) *-4=-1

取模运算的性质

除除法外,模运算与基本的四则运算相似。规则如下:

(a b) % p=(a % p b % p) % p

(a - b) % p=(a % p - b % p) % p

(a * b) % p=(a % p * b % p) % p

^ b % p=((a % p)^b) % p

关联法则:

((a b)% p c)% p=(a b c)% p)% p

((a*b) % p \* c)% p=(a \ (b*c) % p) % p

交换律:

(a b) % p=(b a) % p

(a * b) % p=(b * a) % p

分配定律:

(a b) % p=(a % p b % p ) % p

((a b)% p * c) % p=((a * c) % p (b * c) % p) % p

tips

当我们只关注一个整数的后k位时,可以使用模运算。

例如:

long long x=12345678911

我们只关注这个数的后4位,可以用temp=x% 10^4.

用这个temp代替x等数的四则运算。

二进制与位运算

1.二进制转十进制

例如,二进制101被转换成十进制

\[101==1*pow(2,2) 0*pow(2,0) 1*pow(2,1)==2 1 2==5

\]

2.十进制转二进制

1.5/2=2.一

2.2=2/2.0

3.1=1

反向转换后变成101

3.原码反码补码

image

具体:原码补_张子娃的博客-CSDN博客_原码补

4.""与""运算

image

n1==n/pow(2,1)

n1==n*pow(2,1)

示例:

#includebits/stdc。h

使用命名空间std

int main(){

IOs : sync _ with _ stdio(false);CIN . tie(0);cout . tie(0);

int n;

cinn

cout(n1)' '(n1);

返回0;

}

输入: 6

输出: 3 12

5."~"运算

image

6.""运算

image

素数筛

一般筛选方法:从n到sqrt(n)循环判断,时间复杂度为O2。

艾氏筛

例(板题):P3912素数个数-洛古|计算机科学教育新生态(luogu.com.cn)

解决方案/电路板

#包含位/标准数据。h

使用命名空间std

typedef long long ll

bool A[100000000];//对或错

带符号的main() {

IOs : sync _ with _ stdio(false);CIN . tie(0);cout . tie(0);//c关闭同步流,建议scanf。

int n;

CIN n;

ll CNT=n;//判断数字,默认为N个质数

CNT-;//因为1不是质数,所以cnt先减1

for(int I=2;I * I=n;I) {//Screen from 2 to sqrt(n)//利用root打开的思想进行故障排除。

If (A==false) {//如果A是素数

for(int j=I * 2;j=n;J=i) {//如果当前I是素数,则将它的所有倍数标记为非素数。

if (A[j]==false) {

A[j]=真;e-;

}

}

}

}

cout e endl

}

欧拉筛(OLA)

例(板题):P3383【模板】线性筛选素数-洛古|计算机科学教育新生态(luogu.com.cn)

解决方案/电路板

#包含位/标准数据。h//欧拉筛

使用命名空间std

bool A[100000001];int prime[1000001];

int main(){

IOs : sync _ with _ stdio(false);CIN . tie(0);cout . tie(0);

int n,m;

int CNT=0;

scanf('%d %d ',n,m);

for(int I=2;I=n;i ){

if(A==false){

prime[CNT]=I;

}

for(int j=1;j=cnti * prime[j]=n;j ){

a[I * prime[j]]=true;

if(i%prime[j]==0)破;//最重要的一步

}

}

for(int I=0;im;i ){

int c;scanf('%d ',c);

printf('%d\n ',prime[c]);

}

返回0;

}

米勒罗宾素性测试

【学习笔记】米勒-拉宾素数检验

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now