[C++知识库]C++数论/数学总结

1.数论
整数型问题:整除、最大公约数、最小公倍数、欧几里得算法、扩展欧几里得算法.
素数问题:素数判断、区间素数统计.
同余问题:模运算、同于方程、快速幂、中国剩余定理、逆元、整数分解、同余定理.
不定方程.
乘性函数:欧拉函数、伪随机数、莫比乌斯反演.
2.组合数学
排列组合:技术原理、特殊排列、排列生成、组合生成.
母函数:普通型、指数型.
递推关系:斐波那契数列、Stirling数、Catalan数.
容斥原理、鸽巢原理
群:Polya定理
线性规划:单纯行法.
3.矩阵、线性代数、高精度计算、概率、数学期望、组合游戏、傅里叶变换.

大数加法

大数a+b也就是用字符串输入一串数字代表这个数字的大小，然后模拟一下加法的过程就可以了，为了方便计算把最低位个位放到第一个逆序计算比较方便

		int a[1010],b[1010],c[1010],l1,l2,i,j,n,t,x,y=1;
		char s1[1010],s2[1010];
        scanf("%s %s",s1,s2);
		l1=strlen(s1),l2=strlen(s2);//计算长度
		//初始化数组abc全为0
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		//把字符串s1 s2逆置存入数组a,b，逆序存方便计算
		//就是把个位放到第一位依次往后递推
		for(i=l1-1,j=0;i>=0;i--){
			a[j++]=s1[i]-'0';
		}
		for(i=l2-1,j=0;i>=0;i--){
			b[j++]=s2[i]-'0';
		}
		//这里计算a,b的每一位存入c
		//这里应该就明白为什么把数组abc都初始化为0了把
		//方便计算a+b就算长度不相等也可以利用0弥补，可以模拟一下加法过程。
		//这也就是逆序存储的方便计算，后面加0不影响大小
		for(i=0;i<1005;i++){
			x=a[i]+b[i]+c[i];//如果进位了这里c[i]=1不进位就是0.
			c[i]=x%10;//取余
			c[i+1]=x/10;//进位
		}
		//找到第一个非0数就是最高位数，可以自己思考一下为什么
		for(i=1005;i>=0;i--)
		if(c[i]!=0)
		break;
		if(i==-1)
	    printf("0");
	    //输出计算结果
	    for(;i>=0;i--)
	    printf("%d",c[i]);
	    printf("\n");

大数减法

同大数加法模拟减法过程即可.
这个代码参考大数加法可以写一下.

大数乘法

N的阶乘问题代码:

int i,j,k,s,l=0,n;
    scanf("%d",&n);
    a[0]=1;
    //计算出前n个数的乘积，简单暴力。
    for(i=1;i<=n;i++)
    {
        int x=0,y=0;
        for(j=0;j<10000;j++)
        {
            x=a[j]*i+y;
            y=x/10;
            a[j]=x%10;
        }
    }
    for(i=0;;i++)//循环遍历第一个不为0的数就是计算出来的末尾不为0的第一个数！
    {
        if(a[i]!=0)
        {
            printf("%d\n",a[i]);
            break;
        }
    }

参考链接:质数乘积（大数乘法+埃氏筛法）

模拟乘法过程注意进位

    char aa[50],bb[50];
	int s[100]={0},i,j,f=0,k,l1,l2,x,y,z,a[50],b[50];
	scanf("%s%s",aa,bb);
	l1=strlen(aa),l2=strlen(bb);
	for(i=l1-1,j=0;i>=0;i--)
	a[j++]=aa[i]-'0';
	for(i=l2-1,j=0;i>=0;i--)
	b[j++]=bb[i]-'0';
	for(i=0;i<l2;i++)
	{
		f=0;
		k=i;x=0,y=0;
		for(j=0;j<l1;j++)
	   {
		x=y+a[j]*b[i]+s[k];
		y=x/10;
		s[k]=x%10;
		k++;
	   }
	   if(y!=0)
	   f=1,s[k]=y;
   }
	for(i=k+f-1;i>=0;i--)
	printf("%d",s[i]);
	printf("\n");

大数除法

这个太难,一般都是直接打模板.

大数取模

== 会大数除法自然会取模了==

最大公约数

记住这个函数即可__gcd(x,y)

    x=1000,y=88888;
	cout<<__gcd(x,y)<<endl;//结果是8 

最小公倍数

两个数相乘除以最大公约数即可

	x=1000,y=88888;
	cout<<x*y/__gcd(x,y)<<endl;//结果是11111000

欧几里得算法

gcd( m , n ) = gcd( n = m % n)
直到最后gcd(m , 0)=m,m最后的取值也就是m和n的最大公约数。
用于计算欧几里得算法gcd(m,n)
第一步：如果n=0，返回值m则作为结果。通过计算过程结束，否则进入第二步。
第二步：m除以n，将余数赋值给R；
第三步：将n的值赋给m，将r的值赋值给n。返回第一步
自己敲一下代码吧.

扩展欧几里得算法

扩展欧几里德算法是用来在已知a, b求解一组x和y，使它们满足等式： ax+by =?gcd(a, b) =d(解一定存在，根据数论中的相关定理)。即对于不完全为 0 的非负整数 a，b，gcd(a,b)表示 a，b 的最大公约数，必然存在整数对 x和y，使得 gcd(a，b)=ax+by。
扩展欧几里得算法，精髓在于对x和y的赋值。对于a’ = b,b’ = a % b 而言，我们求得 x,y使得 a’x + b’y = Gcd(a’,b’)由于b’ = a% b = a - a / b * b 那么可以得到:a’x + b’y= Gcd(a’,b’) ，因而bx + (a - a / b * b)，y = Gcd(a’,b’) = Gcd(a,b)进而可得ay +b(x - a / by) = Gcd(a,b)因此对于a和b而言，他们的相对应的p，q分别是y和(x-a/by).

素数判定和区间素数统计

埃氏筛法:

//标记10000以内的素数
    for(i=0;i<=10000;i++)
        b[i]=1;//先把所有数标位1
    for(i=2;i<=100;i++)//前100的质数就能筛出来所有质数了
        {
            if(b[i])//如果b[i]==1则就是素数
            {
               for(j=i+i;j<=10000;j=j+i)//埃氏筛法，所有是i的倍数全部不是素数，标记为0
                b[j]=0;//标记所有不是质数的数
            }
        }

模运算

模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a – b) % p = (a % p – b % p) % p
(a * b) % p = (a % p * b % p) % p
(a^b) % p = ((a % p)^b) % p
结合律：
((a+b) % p + c) % p = (a + (b+c) % p) % p
((ab) % p * c)% p = (a * (bc) % p) % p
交换律：
(a + b) % p = (b+a) % p
(a * b) % p = (b * a) % p
分配律：
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p
重要定理：
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a – c) ≡ (b – d) (%p)，
(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p);

除法取模

设k为b的逆元

(a/b)%m=(ak)%m (自证)

快速幂

假设求a^b%m
首先我们可以参考上面的取模运算
a^b%m = (a%m)^b%m
所以我们运算的时候一直对底数a取余即可
快速幂过程:
即当b为偶数: a^( (b/2)*2 ) 即(a²⁾b/2
这个时候幂数就会除以2了,达到了我们想要的快速效果.
当b不为偶数:可化为:a×a^b-1这个时候b-1一定是偶数哦!!!
上代码!!!

int f(long long a,long long b)
{
    a=a%m;
    long long s=1;
    while(b>0)
    {
        if(b%2==1)//指数为奇数时 
        s=(s*a)%c;//单独×一个底数 
        //这个地方当b为奇数时  b/2和(b-1)/2结果一样
        b=b/2;//指数变为原来的1/2 
        b=(b*b)%h;//底数扩大原来的平方 
    }
    return s;
}

参考题目链接:越狱（快速幂）

参考链接:JAVA大数运算–加减乘除取余