Number theory knowledge

1.快速幂
2^10
= 4^5
=4*16^2
= 4 *256
eg.求a^b

int power(int a,int b)
{
    
    int res=1;
    while(b)
    {
    
        if(b&1) res*=a;
        b>>=1;
        a=a*a; 
    }
    return res;
}

Casting may be required at some point模板例题
2.

a=4*a;//等价于a<<=2
a*=10;//等价于(a<<3)+(a<<1)
a*=15;//等价于(a<<4)-a
11111(30个1)等价于(1<<31)-1

//a,b交换位置
a^=b^=a^=b;

4.Yang Hui's triangle and permutations

5.质数筛

The most common judgment O(n*n^(1/2))

int prime[maxn];
int cnt=0;
prime[++cnt]=2;
prime[++cnt]=3;
for(int i=4;i<=n;i++)
{
    
	int flag=1;
	for(int j=2;j*j<=4;j++)
	{
    
		if(i%j==0)
		{
    
			flag=0;
			break;
		}
	}
	if(flag) prime[++cnt]=i;
}

garbage sieve(埃拉托斯特尼筛法)

bool isprime[maxn];
int prime[maxn];
int cnt=0;
int getprime(int n)
{
    
    for(int i=1;i<=n;i++) isprime[i]=1;
    isprime[1]=0;
    for(int i=2;i<=n;i++)
    {
    
        if(isprime[i])
        {
    
            prime[++cnt]=i;
            if((long long)i*i<n)
            {
    
                for(int j=i*i;j<=n;j+=i) isprime[j]=0;
            }
        }
    }
    rertun cnt;
}

线性筛（欧拉筛）

void getprime()
{
    
    for(int i=2;i<=n;i++)
    {
    
        if (!notprime[i]) prime[++tot]=i;
        for (int j=1;j<=tot&&i*prime[j]<=n;j++)
        {
    
            notprime[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
}

理解：

 if (i%prime[j]==0) break;

text{这一句是关键,如果i=4的话,当prime[j]=2时,标记8不是素数,Then it jumps out of the loop
If you do not jump out of the loop at this time,12will be screened at this time,但
$$4\cdot 3=6\cdot 2=12$$
实际上12应该被2筛掉,That is, it is screened out by his smallest prime number,因此当i是prime[j]should jump out of the loop directly
6.
^可以看成+（Simple notation
1^1=0 1+1=10=0
1^0=1 1+0=0
0^0=0 0+0=0

7.
例题

gcd (grand common divisor,即最大公约数）
(a,b)即求a和b的最大公约数
(a,b)=(b,b%a)
证明：
$$\begin{gathered} a=k_1\cdot c \\ b=k_2\cdot c \end{gathered}$$
即(a,b)=（$k_1\cdot c,b=k_2\cdot c$）
所以($k_1,k_2$)=1
$$\begin{gathered} b=k_2\cdot c=k_3\cdot d \\ a\mathrm{mod}b=(k_1,k_2)\cdot c=c \end{gathered}$$

int gcd(int a,int b)
{
    
    if (!b) return a;
    return gcd(b,a%b);
}

int gcd(int a,int b)
{
    
    while (b)
    {
    
        int t=b;
        b=a%b;
        a=t;
    }
    return a;
}

#include <algorithm>
__gcd(x,y);

9.还需理解
逆元
eg.
3*4=1(mod11)
这里4是3的逆元,相当于1/3
oiwikiThe inverse element explanation of