算法数学知识(一)

求出一个数的所有约数

#include
#include
using namespace std;
vector<int> v;
int main()
{int n;cin>>n;// 求出n的所有约数for(int i=1;i*i<=n;i++){if(n%i==0){v.push_back(i);if(n/i!=i) v.push_back(n/i);}}// 遍历n的所有约数for(auto i = v.begin();i!=v.end();i++) cout<<(*i)<<' ';return 0;
}

判定法求质数(素数)

模板:

//试除法
bool is_prime(int x)
{if (x < 2) return false;//最小的质数是2//以12为例,当i=2时,i<=6,当i=3时,i<=4,当i=4时,i<=3退出for循环//12=2*6，只要判断12/2即可判定其为合数，无需再进行下面的判断for (int i = 2; i <= x / i; i ++ )if (x % i == 0)return false;return true;
}
//acwing

例题
给定 n 个正整数 ai，判定每个数是否是质数。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式
共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。

数据范围
1≤n≤100,
1≤ai≤231−1
输入样例：

2
2
6

输出样例：

Yes
No

#include 
#include using namespace std;bool is_prime(int x)
{if (x < 2) return false;for (int i = 2; i <= x / i; i ++ )if (x % i == 0)return false;return true;
}int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;if (is_prime(x)) puts("Yes");else puts("No");}return 0;
}

分解质因数

质因数就是一个数的约数，并且是质数。
质数又称素数，正因数只有1和它本身
1既不是质数也不是合数
模板

//试除法
void divide(int x)
{for (int i = 2; i <= x / i; i ++ )if (x % i == 0){int s = 0;while (x % i == 0) x /= i, s ++ ;//相同的因数可以不止有一个//比如8=2*2*2cout << i << ' ' << s << endl;}if (x > 1) cout << x << ' ' << 1 << endl;//质数情况,此时若x>1说明x是质数cout << endl;
}
//acwing

例题
给定 n 个正整数 ai，将每个数分解质因数，并按照质因数从小到大的顺序输出每个质因数的底数和指数。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个正整数 ai。

输出格式
对于每个正整数 ai，按照从小到大的顺序输出其分解质因数后，每个质因数的底数和指数，每个底数和指数占一行。

每个正整数的质因数全部输出完毕后，输出一个空行。

数据范围
1≤n≤100,
2≤ai≤2×109
输入样例：

2
6
8

输出样例：

2 1
3 12 3

#include 
#include using namespace std;void divide(int x)
{for (int i = 2; i <= x / i; i ++ )if (x % i == 0){int s = 0;while (x % i == 0) x /= i, s ++ ;cout << i << ' ' << s << endl;}if (x > 1) cout << x << ' ' << 1 << endl;cout << endl;
}int main()
{int n;cin >> n;while (n -- ){int x;cin >> x;divide(x);}return 0;
}

筛质数

模板

//线性筛法求素数
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉void get_primes(int n)
{for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] <= n / i; j ++ ){st[primes[j] * i] = true;if (i % primes[j] == 0) break;}}
}
//acwing

线性筛法核心：
每个合数是被其最小的质因数给筛掉的
每个被筛掉的合数，只被筛掉一次，而不是多次

因为6%2==0
说明6能继续拆分成2 * 3,如果要是以3 * 6来筛掉18时就不满足最小质数来筛除的条件了
因为18应该由2*9筛掉，而不是3 * 6,所以此时要break

例题
给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式
共一行，包含整数 n。

输出格式
共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围
1≤n≤106
输入样例：

8

输出样例：

4

#include
using namespace std;
const int N=1000010;
int primes[N],cnt;//primes存放当前已经筛选出来的质数
bool st[N];//存放是否被筛选掉int fun(int n){for(int i=2;i<=n;i++){//质数从2开始if(!st[i]){//如果没有被筛掉说明是质数primes[cnt++]=i;//将质数保存在primes数组}for(int j=0;primes[j]<=n/i;j++){//减少for循环的次数，如果是j<=cnt,会造成primes[j]*i>n且会多执行几次st[primes[j]*i]=true;//用当前最小的质因数来筛掉合数//如6=2*3,6被2筛掉，而不是被3筛掉//i%primes[j] ==0说明i能分解成质因数*的形式//如4能分解成2*2,这时就不用用4筛某个数，而是2if(i%primes[j] ==0) break;}}return cnt;
}int main()
{int n;cin>>n;cout<<fun(n);return 0;
}

最大公约数

模板

//欧几里得算法
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
//acwing

例题
给定 n 对正整数 ai,bi，请你求出每对数的最大公约数。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一个整数对 ai,bi。

输出格式
输出共 n 行，每行输出一个整数对的最大公约数。

数据范围
1≤n≤105,
1≤ai,bi≤2×109
输入样例：

2
3 6
4 6

输出样例：

3
2

#include
#include
using namespace std;//欧几里得算法总结：
//1.大数除以小数
//2.上一个算式的除数作为当前算式的被除数,余数作为除数
//3.重复上述步骤，直至余数为0时的除数为最大公约数
int gcd(int a,int b){return b?gcd(b,a%b):a;
}
int main()
{int n;cin>>n;for(int i=0;i<n;i++){int a,b;cin>>a>>b;cout<<gcd(max(a,b),min(a,b))<<endl;}return 0;
}

求组合数

模板
递归法求组合数

// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )for (int j = 0; j <= i; j ++ )if (!j) c[i][j] = 1;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;//公式
//acwing

例题：
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(10的9次方+7) 的值。

输入格式
第一行包含整数 n。

接下来 n 行，每行包含一组 a 和 b。

输出格式
共 n 行，每行输出一个询问的解。

数据范围
1≤n≤10000,
1≤b≤a≤2000
输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

#include
using namespace std;
const int N=2010,mod=1e9+7;
int c[N][N];
void init()
{//c[a][b]表示从a个苹果中选b个的方案数//先进行预处理//预处理过后直接用即可for(int i=0;i<N;i++){//for(int j=0;j<=i;j++){if(!j) c[i][j]=1;else c[i][j]=(c[i-1][j]+c[i-1][j-1]) % mod;}}
}
int main()
{init();int n;cin>>n;for(int i=0;i<n;i++){int a,b;cin>>a>>b;cout<<c[a][b]<<endl;}return 0;
}

快速幂

快速求解

将a的k次方中的k以二进制的形式表示，然后k=2的0次方+2的一次方+…
5=(101)二进制,5=2的0次方+2的2次方

2的1次方=(2的0次方)平方,2的2次方=(2的1次方)平方

模板

typedef long long LL;LL qmi(int a,int k,int p){LL res = 1%p;//res为返回的结果while(k){if(k & 1) res = res * a %p;a=a*(LL)a%p;k>>=1;}return res;
}

例题

#include
using namespace std;typedef long long LL;LL qmi(int a,int k,int p){LL res = 1%p;//res为返回的结果while(k){if(k & 1) res = res * a %p;//如果当前b的二进制写法中最后一位是1//假设a=4,4的1次方=4的2的0次方，4的2次方=4的2的1次方=(4的2的0次方)平方a=a*(LL)a%p;//假设a是4,4的5次方二进制可以表示为4(101)次方,4就是(001)次方,4*4就是(010)次方//又移1位k>>=1;}//对于mod解释，以4的5次方为例，4的5次方mod10=(4mod10)*(4mod10)...=(4*4mod10)*...*(4mod10)return res;
}int main()
{int n;cin>>n;for(int i=0;i<n;i++){int a,k,p;scanf("%d%d%d",&a,&k,&p);cout<<qmi(a,k,p)<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！