本帖持续更新
这是编程算法计算加速总结

快速乘法

思路

假设当前计算a*b,应用二进制，将a,b中较大的一位数转化为二进制表示，例如11转化为1011，然后类比利用竖式计算乘法那样，用较小的数乘以每一位代表的2次幂，最后相加。

加速点

乘法转为logn量级的乘法+加法

代码

无取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
unsigned long long Imul(unsigned long long a, unsigned long long b)
{
	if (a > b)
	{
		unsigned long long tmp = a;
		a = b;
		b = tmp;
	}
	unsigned long long x = 0;
	while (b != 0)
	{
		if ((b & 1) == 1)
		{
			x = x + a;
		}
		a = a * 2;
		b >>= 1;
	}
	return x;
}

取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
unsigned long long Imul(unsigned long long a, unsigned long long b,unsigned long long mod)
{
	if (a > b)
	{
		unsigned long long tmp = a;
		a = b;
		b = tmp;
	}
	unsigned long long x = 0;
	while (b != 0)
	{
		if ((b & 1) == 1)
		{
			x = (x + a) % mod;
		}
		a = (a * 2) % mod;
		b >>= 1;
	}
	return x;
}

快速幂

思路

类似于快速乘法，同样利用二进制，这里利用的是幂次的二进制位。
例如： $ 7^{11} $ ,幂次的二进制位为:1011，因而可以拆分为： ${7^8} \times {7^2} \times 7$ ，而这些幂次都可通过7的不断自乘得到。只需乘6次即可得到结果。

加速点

利用二进制的特性，直接不断自乘本身即可得到结果，可以跳过一些次幂的运算。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
M* Mpow(M* m, unsigned long long n)
{
	M* ans = new M(1, 0, 0, 1);
	while (n != 0)
	{
		if ((n & 1) == 1)
		{
			ans = Mmul(ans, m, mod);
		}
		m = Mmul(m, m, mod);
		n = n >> 1;
	}
	return ans;
}

快速斐波那契数列

思路

$$\left[ {\matrix{ {f(2)} & {f(1)} \cr 0 & 0 \cr } } \right] \times {\left[ {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right]^{n - 2}} = \left[ {\matrix{ {f(n)} & {f(n - 1)} \cr 0 & 0 \cr } } \right]$$

其中， ${\left[ {\matrix{ 1 & 1 \cr 1 & 0 \cr } } \right]^{n - 2}}$ 可以用快速幂计算

代码

1
2
3
4
5
6
7
unsigned long long fib(unsigned long long i)
{
	M* A = new M(1, 1, 0, 0);
	M* B = new M(1, 1, 1, 0);
	M* ans = Mmul(A, Mpow(B, i - 2));
	return ans->data[0][0];
}

快速斐波那契求和

公式

$$\sum\limits_{i = 1}^n {f(i)} = f(n + 2) - 1$$

买不到的数目

题目

小明开了一家糖果店。他别出心裁：把水果糖包成 4 颗一包和 7 颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是 17。大于 17 的任何数字都可以用 4 和 7 组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

结论

对于方程

1.a,b互质，一定有解且解的数目无穷
2.C是gcd(a,b)的倍数，方程一定有解，且有无穷多解

对于本题

最大不能组合出的数字：n*m-n-m

公约数公倍数

公约数——欧几里得法

思路

假如x,y有最大公约数T，根据最大公约数的定义，则x,y都可以被T整除。同时也有这样一个数学规律:
$$C = {\rm{mx}} \pm {\rm{ny}}$$
这样的C也是可以被最大公约数T整除的。那么假设：
$$\eqalign{ & x > y,x \div y = a...b \cr & {\rm{b}} = x - a \times y \cr} $$
那么b也是可以被T整除的，这个b小于y,那么我们得到新的两个数，新的x（较大的这个）为y（旧y），新的y为b，这两个的数仍然可以被T整除，且这两个数均小于原数。
我们这样一直重复，会使得x,y越来越小，越接近T，最后成为T：
$$x\% y = 0$$
此时x=y为最大公约数。

公倍数——公约间接法

思路

假设x,y为两数，T为最大公约数，M为最小公倍数，有这样的数学公式：
$$xy = TM$$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void myfunc(int a, int b)
{
   int m,n,r;  
   if(a<b) swap(&a,&b);
   m=a;n=b;r=a%b;
   while(r!=0)
   {
    a=b;b=r;
    r=a%b;
   }
   printf("%d\n",b);  // 最大公约数 
   printf("%d\n",m*n/b);  // 最小公倍数 
}