写在最前面：
此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。
质数
质数的判定（试除法）
质数的定义：
- 大于1。
- 只有1和它本身两个约数。
所以，只要满足这两个条件的都是质数。可以根据这个来判断一个数是不是质数。特别的，在判断条件2时，可以采用试除法，即尝试从i=2开始所有偏小的所有数字（如果一个数字有约数，那么只算对应两个约数较小的一方，如1 * 2=2，则只算1），判断是否满足条件。
下面是模板：
bool isprime(int n)
{
if (n<2) return false;
for(int i=2; i<=n/i; i++) //算sqrt计算速度较慢，i*i结果可能溢出
if(n%i==0) return false;
return true;
}
分解质因数（试除法）
每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数。————选自百度百科
简单来说就是把一个数字分解为几个质数相乘。一个数字最多有一个大于根号n的质因子。
下面是模板：
void divide (int n)
{
for(int i=2; i<=n/i; i++)
{
if(n%i==0)//这个方法保证了全部都是质数，因为在上一次递归中已经把含有质因子的数字除掉了
{
int s=0;
while (n%i==0)
{
s++;
n/=i;
}
printf("%d %d\n",i,s);//底数i指数s
}
}
if(n>1) printf("%d %d\n",n,1);//一个数字至多有一个质因子大于sqrt（n）
puts("");
}
筛选质数
筛选在n范围里面的所有质数。
埃氏筛法
从2开始，判断后面的数字是否为2的倍数，是则删除；判断完所有的数字是否为2的倍数之后判断是否为3的倍数，以此类推。
下面是模板：
int num;
bool str[N];//不为质数为true，否则为false（默认false）
void judgeprime(int n)
{
for(int i=2; i<=n; i++)
{
if(!str[i])
{
num++;
for(int j=i+i; j<=n; j+=i) str[j]=true;
}
}
}
线性筛法
先判断该数字是否在前面被判断为合数，然后循环判断存质数的数组内所有数字 * i均为合数，遇到i的第一个最小质因子停止。
速度在算1e7以上的数据时比埃氏筛法要快一倍。
int cnt,prime[N];
bool st[N];//不为质数为true，否则为false（默认false）
void getprime(int n)
{
for(int i=2; i<=n; i++)
{
if(!st[i]) prime[cnt++]=i;
for(int j=0; prime[j]<=n/i; j++)
{
st[prime[j]*i]=true;
if(i%prime[j]==0)break;//prime[j]一定是i的最小质因子
}
}
}
约数
试除法求所有约数
和上面类似。遍历，然后把所有约数存进vector里面。
下面是模板：
#include <bits/stdc++.h>
using namespace std;
vector <int> get(int n)
{
vector <int>res;
for(int i=1; i<=n/i; i++)
{
if(n%i==0)
{
res.push_back(i);
if(i!=n/i)res.push_back(n/i);//排除n是i方的情况
}
sort (res.begin(),res.end());
}
return res;
}
int main()
{
int n;
scanf("%d",&n);
while (n--)
{
int x;
scanf("%d",&x);
auto res=get(x);
for(auto t: res) cout <<t<<" ";
cout << endl;
}
return 0;
}
约数个数、约数之和
一般的，一个数字可以化为x=a1^p1 * a2^p2 * …… an^pn的形式，ai均为质数。
约数个数：
一个约数a1有（p1+1）种选法（即a1^0……a1^p1）,a2有（p2+1）种选法，以此类推，一共有（p1+1）(p2+1)……(pn+1)种选法。于是反过来看，一共就有（p1+1）(p2+1)……(pn+1)个约数。
特别的，int范围内的数字约数约为1500左右。
下面是模板：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//n个整数的乘积的约数个数
int main()
{
int n,num;
scanf("%d",&n);
unordered_map<int,int> prime;
while (n--)
{
scanf("%d",&num);
for(ll i=2; i<=num/i; i++)
{
while (num%i==0)
{
prime[i]++;
num/=i;
}
}
if(num>1)prime[num]++;
}
ll res=1;
for(auto x:prime)
res*=x.second+1;
printf("%lld\n",res);
return 0;
}
约数之和
(a1^0+a1^1……+a1^p1)(a2^0+a2^1……+a2^p2)……(an^0+an^1……+an^pn) 把上面这个式子拆分开得到的就是所有约数的和，原理和上述约数个数相似。
下面是模板：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,num;
scanf("%d",&n);
unordered_map<int,int> prime;
while (n--)
{
scanf("%d",&num);
for(ll i=2; i<=num/i; i++)
{
while (num%i==0)
{
prime[i]++;
num/=i;
}
}
if(num>1)prime[num]++;
}
ll res=1;
for(auto x:prime)
{
int a=x.first,p=x.second;
ll t=1;
while (p--) t=(a*t+1);//假设t为1，那么乘第一次为p+1，第二次p*（p+1）+1，为p^2+p+1以此类推，获得条件
res*=t;
}
printf("%lld\n",res);
return 0;
}
最大公约数
欧几里得算法（辗转相除法）
定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。————选自百度百科
gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)
证明：
定理：如果d/a和d/b均能整除，那么d/（a+b）也可以整除，d/（a * c1 + b * c2）也可以整除。（c1，c2均为常数。）
证明左面等于右面：b=b，a % b=a-a/b * b;a/b为整除，用整数c代替。那么a % b=a-c * b，满足定理，所以a%b=a；
证明右边等于左边：b=b。a%b=a-c * b。那么（a-c * b）+ c * b=a满足定理。
下面是模板：
#include <iostream>
#include <cstdio>
using namespace std;
int gcs(int a,int b)
{
return b?gcs(b,a%b):a;
}
int main()
{
int n;
cin >> n;
while (n--)
{
int a,b;
cin>>a>>b;
printf("%d\n",gcs(a,b));
}
return 0;
}
京公网安备 11010502036488号