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比赛完了后怎么办


下一篇:看看谁获得了CodeM编程大赛的10万奖金