算法 : 数论
数学基础内容：最大公因数，最小公倍数， 余数相关(同余？) 进制转换 位运算
1.质数筛法
1~~10之间的质数 2，3，5，7
1~~10000之间的质数
朴素算法(暴力)： O(n^2)
优化：判断是否是质数，我们知道因式都是成对出现的 i=m*n
假设m<=n,如果m是i的因式，那n不需要判断，一定是i的因式。
意思就是说我只需要判断小的(<sqrt(x)) 大的不需要判断了
所以优化：
于是时间复杂度降低为O(x^1.5)
还能不能再降低一点呢？ 那就不能用暴力了，需要数学方法
埃式筛法
基本原理：算数基本定理/唯一分解定理
一个合数是可以被分解成若干个质数的乘积的，并且是唯一的 eg 24=2*2*2*3 110=2*5*11
一个质数的倍数一定是合数
利用这个特点，我们可以通过从最小的质数2开始遍历到n，每次将2的倍数的数字标记为合数。
到最后剩下未被标记的数字就一定是质数了
#include <iostream>
using namespace std;
//埃式筛法
//一个合数可以写成若干质数的乘积，质数的倍数一定是合数
int sum; //统计质数个数
int p[10005]; // p[i]=j 第i个数字j是质数
int isprime[10005]; //isprime[i]=0 表示数字i是质数 =1 表示数字i是合数
//一开始所有数字都是质数
int main(int argc, char** argv) {
int n;
cin >> n;
isprime[1] = -1;
for (int i = 2; i <= n; i++)
{
if (!isprime[i]) //如果i是质数
{
p[++sum] = i;
cout << p[sum] << " ";
for (int j = i * 2; j <= n; j += i) //从i的二倍开始找i的倍数，更新为合数
{
isprime[j] = 1;
}
}
}
cout <<endl<< sum;
return 0;
}
时间复杂度O(n*log(logn))
但它仍有缺陷：同一个数字（eg.110）可能会被标记多次
我们希望一个合数只被它最小的那个因子标记一次。遍历2~n，是合数则标记一次，是质数则保存
最后时间复杂度会变成O(n)的
欧拉筛法/线性筛
原理：规定一个合数只会被它最小的质因数筛去。这个最小的质因数一定小于它本身
又 一个合数是可以被分解成若干个(至少两个)质数的乘积的 假设a是最小的质因数，y是要被筛掉的合数
两者结合起来可以得到 被a筛掉的合数y满足—->y>=a^2 =a*a
eg.被因数3筛掉—- 满足>=9 被因数7筛掉—->满足 >=49
有什么用呢？下次枚举筛掉合数时，就直接从a的a倍开始筛，这样就能保证每个合数只被它最小的质因数筛去
下次枚举
总结：难以理解就背：外循环既是判断的数据，又是倍数。 内循环遍历质数表，乘以倍数
这里好好琢磨一下
2.快速幂
求a^n O(n) —>logn n很大
eg 5^n =(5*5)*(5*5)*(5*…..=(25*25)*25*……= 625*625*…..
a=5 =5^1 1=2^0
a*=a =5^2 2=2^1 第一次
a*=a =5^4 4=2^2 第二次
a*=a =5^8 8=2^3 第三次
原因a=a*a=a^2
那么5^n，n=？ n=2^i i=logn
既然这样:
1.如果n是2的若干次幂，我们可以自己乘以自己计算得到n,计算5^n 。时间复杂度是： O(logn)
2.进制转换：任何正整数都可以写成2^n相加的形式<——->二进制可以做运算转化为十进制
1,2结合：快速算出a^x x为任意正整数，并且复杂度为logn
a^x=
方法：把x写成2^n相加的形式，把这个东西带到a里面去
eg.19=16+2+1—-> a^x=a^19=a^(16+2+1)=a^16*a^2*a^1
指数相加————– ———- 幂数相乘
欸，16，2，1就利用结论二转化为了结论一的形式—->2的若干次方，自己乘自己
另外， 19=16+2+1 是由二进制得出来的。
1 0 0 1 1
16 8 4 2 1
a^16 a^2 a^1
所以就可以在计算指数x的二进制的时候让a自己乘自己，把这些2的若干次幂给求出来
然后在二进制数字是1时就把a^i乘进去
ll sum=1; //保存最终结果
while(x!=0)
{ if(x%2==1) sum=(sum*a)%p; //只有答案是1的时候，二进制的若干次数才会出现在答案中
x/=2;
} a=(a*a)%p; //下一位二进制位对应的a^i
return sum;
时间复杂度O(logx)
如下图
总结题目：
快速幂—–>一般不会单独出题， 是某个题目的中间步骤
a^x x一般会很大，x>10^8 ，在计算过程中就可能超出数据范围，所以题目会要求进行模运算
sum=(sum*a)%p ;
同余方程
快速幂记不住怎么办
- 现在纸上把这个式子给写出来
然后凭借模糊的记忆，你知道 3^1→3^2→…→3^16是可以用自乘依次得到
再来跟二进制有关，可是为什么要求二进制呢？ 哦！当只有比特为1的时候再乘进去
- 最后要注意有没有取模操作
- 当然自己成自己前提是你知道底数
int s=1; //存储当前幂的数字
int res = 0;
while (!st.empty())
{
if(st.top()!=0)
res += s * st.top();
st.pop();
if(s==1) s=d;
//else s*=s;
else s*=d ;//当前位的幂方数字 ，别弄混了
}
//cout << res << " ";
return res;
3.高精度(加减乘除)—>大数运算
总结类型变化： string存储大数—–>int数组倒序存储数字—->各种操作—–>倒序存储/string倒序输出
存储：
10^12—–>13位数 10^10000—->10001位数
long long b=10^12 c=10^10000 没有任何数据类型可以存放
对于大数，我们把它们当作字符串保存
char a[10001]="1000….000"
string s="1000…000" 字符串的比较 "abc"<"acb" "ac">"abc" "abc">"ab"
加减运算：
10^10000+10^1000=?
字符串模拟运算： 100….0
+ 1….0 并且保证位数对齐
因为两个字符串的长度都不一样，个位上的数字也不好对齐，所以选择倒着转化到int类型数组
a[0]存个位，a[1]存十位
补充：结果c的最大位数 max(a,b)+1
所以本质还是模拟题
注意细节：
去掉前导0：
//模拟两个不超过一万位的数字相加，相减
//测试用例： 0011+0022 33 0022-0022=0 0012- 0032=-20
#include<iostream>
#include<string>
using namespace std;
int a[10005], b[10005], c[10005], d[10005];
int change(string m, int* n)
{
for (int i = 0; i < m.size(); i++)
{
n[i] = m[m.size() – 1 – i] – '0'; //int类型哦
}
return m.size();
}
void Plus(int len1, int len2) //模拟相加
{
int lc = max(len1, len2) + 1; //lc最大位数是a,b中最大的位数+1
for (int i = 0; i < lc; i++)
{
c[i] += a[i] + b[i];
if (c[i] >= 10)
{
c[i] -= 10;
c[i + 1]++; //进位
}
}
//倒着输出即是答案，但需要先去掉前导0
while (c[lc – 1] == 0 && lc >1) //既要去掉前导0，又要保证最多输出一个0
{
lc–;
}
for (int i = lc – 1; i >= 0; i–)
{
cout << c[i];
}
}
void Abst(int len1, int len2, bool ifab)
{
int ld = max(len1, len2);
//先判断谁大谁小，避免减出负数
if (!ifab) cout << "-";
for (int i = 0; i < ld; i++)
{
d[i] += a[i] – b[i];
if (d[i] < 0)
{
d[i] += 10;
d[i + 1]–;
}
}
//倒着输出即是答案，但需要先去掉前导0
while (d[ld – 1] == 0 && ld > 1) //既要去掉前导0，又要保证最多输出一个0
{
ld–;
}
for (int i = ld – 1; i >= 0; i–)
{
cout << d[i];
}
}
int main()
{
//先用string类型存储大数为字符串
string m, n;
cin >> m >> n;
bool ifab = stoi(m) > stoi(n) ? 1 : 0;
if (!ifab) m.swap(n); //如果m<n，相减时应该让b-a
//再将字符串倒着转换到Int类型的数组当中
int la = change(m, a);
int lb = change(n, b);
//正序进行模拟运算
Plus(la,lb);
//Abst(la, lb, ifab);
}
高精度乘除法：
两个最多一万位数相乘(保证是正整数)
字符串读入—->倒着转化到int数组中存储—->用数组去模拟乘法的竖式运算—->去前导0，倒着输出结果
1.边算边进位比较麻烦，可以先加到c数组后再进行进位操作
2.n位*m位结果位数最多是m+n 证最大的三位数999*最大的二位数99==五位数
3.b[i]*a[j]= c[i+j] 放在了下标i+j位置
所以我们大可简化，
（1）每次遍历b[i]*a[j]直接放到c[i+j]的位置。
(2)遍历完后再遍历c数组进行进位 0~lc:如果a[i]>10 a[i+1]+=a[i]/10; a[i]%10
(3)去掉前导0
高精度除法：
我们规定：相除如果有余数，结果向下取整
较小的数/较大的数=0
于是有三个问题：
1.怎么将a数组前面那三位提出来与b数组相除
把b数组往前移x位放入t数组，使之长度与a数组相同 便进行相除操作
2.如何计算得到答案4？ 数据放入数组无法进行除法
高精度减法—-我循环做减法，直到上面的数小于下面的数，而减去的次数就是答案
3.怎么将第一个结果4放入到c的位置 ？
商的长度：a的长度为n，b的长度为m，c的长度是 max(n-m+1,0)
所以算出来直接把结果放入lc-1(下标为0)
执行完一次，移动b得到与531518长度相同的t，循环减法得到答案4，得到余数 29518，4放入了5-3+1的位置
4.GCD(最大公因数)和GLM(最小公倍数)
// 手动实现GCD（欧几里得算法，迭代版）
int my_gcd(int a, int b) {
a = std::abs(a);
b = std::abs(b);
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
// 基于GCD计算LCM
int my_lcm(int a, int b) {
if (a == 0 || b == 0) return 0; // 处理0的情况
return (std::abs(a) / my_gcd(a, b)) * std::abs(b); // 先除后乘防溢出
}
