数论部分

自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;

注意：除法取模需要用到逆元 与上述式子不符。

快速幂

aⁿ–>a^n/2*a^n/2
若n为偶数，直接进行，若n为奇数，返回a^n/2*a^n/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;
}