目录

质数（素数）

经典问题：给定n个正整数ai，判定每个数是否是质数

（0）暴力遍历（O（N））

（1）试除法判定素数（O(sqrt(N)）

经典问题：给出一个数n，求1~n内素数的个数

（1）朴素筛法求素数

（2）线性筛

分解质因数——试除法（O(sqrt(N)*logN)）

经典问题：差分数字->质数^指数

约数

（1）试除法求约数

（2）约数个数 

（3）约数之和 

欧几里得算法（辗转相除法）

欧拉函数

筛法求欧拉函数

 费马定理

 快速幂

快速幂求逆元

 扩展欧几里得算法

 线性同余方程（拓展欧几里得的应用）

中国剩余定理

质数（素数）

经典问题：给定n个正整数ai，判定每个数是否是质数

注意：2是最小的素数（质数），1不是素数（质数）

（0）暴力遍历（O（N））

#include
using namespace std;
bool is_prime(int n)
{if (n < 2) return false;for (int i = 2; i < n; i++){if (n % 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）试除法判定素数（O(sqrt(N)）

思想：如果d是n的因子，那么n/d也是n的因子，故i的枚举范围可以缩小到2~i<=(n/i)

即可写成i<=(n/i)

#include
using namespace std;
bool is_prime(int n) 
{if (n < 2) return false;for (int i = 2; i <= n / i; i++)//为什么这里需要写“=”？{if (n % 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;
}

问：为什么is_prime函数的第二个for位置需要写“=”？

答：避免平方数的情况：比如说“4”，如果不写“=”，那么将不会执行for循环的语句，return true

问：为什么is_prime函数的第二和for位置不能写成i*i<=n 或者 i<=sqrt(n)?

答：i*i在i接近int范围时容易溢出，i<=sqrt（n）需要每次计算时调用库函数，降低运行效率

经典问题：给出一个数n，求1~n内素数的个数

（1）朴素筛法求素数

思路：

需要两个数组，一个为primes:存放素数，一个为st数组：判断是否为素数

同样是以i为间隔，标记i的倍数为true，那么就确定了这些i的倍数不是素数

模拟过程：

因为全局变量未初始化均为0，所以st[2]=0，可以通过if判断，并将i=2进入primes数组，然后遍历标记i的倍数，为true，那么相当于第一层for循环遍历到4时，将不会执行if判断，因为st[4]=true；如果一个数，从未被标记过，证明前面的数都不是它的因子证明了它就是质数

#include
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n) 
{for (int i = 2; i <= n; i++){if (!st[i]) {primes[cnt++] = i;for (int j = i + i; j <= n; j += i) st[j] = 1;//间隔}}
}
int main() 
{int n;cin >> n;get_primes(n);cout << cnt;
}

（2）线性筛

思路与上面的朴素筛法差不多，都是标记倍数，不过线性筛每次时标记离自己最近那个倍数

#include
#include
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)//12
{for (int i = 2; i <= n; i++) {if (!st[i])//如果没有被标记过：证明时素数{primes[cnt++] = i;//primes[0]=2  primes[1]=3}for (int j = 0; primes[j] <= n / i; j++){//st[4]=1  st[6]=1 st[9]=1st[primes[j] * i] = 1;//遍历素数数组，标记素数的i倍为trueif (i % primes[j] == 0) break;//2%2==0  3%3==0 意思时遍历到最后primes数组的最后一个数了 break}}
}
int main() 
{int n;cin >> n;get_primes(n);cout << cnt;return 0;
}

分解质因数——试除法（O(sqrt(N)*logN)）

经典问题：拆分数字->质数^指数

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

另外有性质，n中最多只包含一个大于sqrt(n)的质因子，所以我们只需要枚举[ 2 , n ] 质因子，然后特判一下n最后是否大于1就可以了

 模拟过程：

（1）我们假设n=6

（2）此时第一次for循环为：for(i=2;i<=3;i++)（注意此时n的值并未发生改变）

（3）执行if(6%2==0) ->(此时我们只能得出2是它的约数，当然实际上2也是质数)

（4）定义次数变量s，进入while循环，当n不是i的倍数时跳出

······

              n=6/2=3         s=0+1

（5）此时跳出 输出质因子2的次数为1  ->也就是6中2只出现1次

经过上次的循环：n=3，那么再进入for循环，i++，所以for(i=3;i<=1;i++)

不执行for循环将最后的因子直接加入        《i=3  s=1》

 核心：本题是用了标记法：对于一个正整数N，如果遍历到了一个它能整除的数，比如说2，那么这个数就会一直除2，直到这个数变为了不能整除2的时候，就跳出循环，此时记录下它的因子和次数，这个操作相当于遍历到2：并将2的所有倍数删除，接着遍历到3，并将3的所有倍数删除，接着遍历到4，此时n一定不能整除4，因为如果它能被4整除，那么它一定能被2整除，所以不执行if（n%i）

这样就保证了每次的i均为质数

#include
using namespace std;
void divide(int n) 
{for (int i = 2; i <= n / i; i++) {if (n % i == 0) {//i一定是质数，因为此时2到i-1的质因子已经被除干净了 int s = 0;//计算次数 while (n % i == 0) {n /= i;//i为什么是质数的原因s++;}printf("%d %d\n", i, s);}}if (n > 1) printf("%d %d\n", n, 1);//特判：当有一个比较大的质因子时cout << endl;}
int main() 
{int n;cin >> n;while (n--) {int x;cin >> x;divide(x);}return 0;
}

约数

正整数中质数以外的数就是约数了^  ^

（1）试除法求约数

给定n个正整数x，对于每个整数x，请你按照从小到大的顺序输出它的所有约数

注意：提升效率的点：i<=(n/i) ，和push_back(i)，且push_back(n/i)   同时操作两个

#include
#include
#include
using namespace std;
vector get_divisors(int n) 
{vector 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);}}sort(res.begin(), res.end());return res;
}
int main() 
{int n;cin >> n;while (n--) {int x;cin >> x;auto res = get_divisors(x);for (auto i : res) {cout << i << " ";}cout << endl;}return 0;
}

问：为什么要加上一个if (i != n / i) res.push_back(n / i)？这个if的作用是什么？

答：if是用来判断i*i！=n，这样就清晰很多了，就是判断n为平方数时的情况，会重复添加i元素

（2）约数个数 

 这里需要用到两个公式：

一个数N分解质因数为如下形式：

 约数的个数公式为：

 图片来源：[AcWing]870. 约数个数（C++实现）求约数个数模板题_cloud的博客-CSDN博客_c++求约数个数

 原理在这篇大佬的博客就有

概括一下就是：得到质因数的出现次数

那么对于出现次数而言的范围是0~最高次数（也就是求出的afa）

因为对于每个数而言，既然它都是质因数，那么我可以选0次，也可以选最高次数次

所以是afa+1，再乘以其他数的（次数总和+1）即可

#include
#include
using namespace std;
const int mod = 1e9 + 7;
typedef long long ll;int main() 
{int n;cin >> n;ll ans = 1;//因为要连乘，所以初始化为1unordered_map hash;while (n--) {int x;cin >> x;for (int i = 2; i <= x / i; i++) {while (x % i == 0) {x /= i;//分解质因数hash[i]++;//质因数的指数++（次数即指数）}}if (x > 1) hash[x]++;//保留最后一个质因数}for (auto &i : hash) ans = ans * (i.second + 1) % mod;//约数公式cout << ans;return 0;
}

（3）约数之和 

 公式原理：

因为拆开任何一项，都是一个约数，相加便是约数之和。（这个公式是将所有约数相加后提取公因数得到的）

[AcWing]AcWing 871. 约数之和 （C++实现）约数之和模板题_cloud的博客-CSDN博客_约数之和c++

#include 
#include 
#include using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;int main()
{int n;cin >> n;unordered_map primes;while (n--){int x;cin >> x;for (int i = 2; i <= x / i; i++)while (x % i == 0){x /= i;primes[i] ++;}if (x > 1) primes[x] ++;}LL res = 1;// ------------------约数之和公式-------------------------for (auto p : primes){LL a = p.first, b = p.second;LL t = 1;while (b--) t = (t * a + 1) % mod; // while (b -- ) t = (t * a + 1) % mod; 是什么意思？res = res * t % mod;}cout << res << endl;return 0;
}

欧几里得算法（辗转相除法）  

[AcWing]872. 最大公约数 （C++实现）最大公约数模板题_cloud的博客-CSDN博客

 核心：gcd(a,b)=gcd(b,a%b)

分两种情况：

（1）当b==0时，0与任意一个数的最大公约数都是它本身

（2）当b!=0时就是gcd(a,b)=gcd(b,a%b)

#include
#include
using namespace std;
int gcd(int a, int b)
{return b ? gcd(b, a % b) : a;
}
int main()
{int n;cin >> n;while (n--){int a, b;cin >> a >> b;cout << gcd(a, b) << endl;}return 0;
}

欧拉函数

经典问题：给定n个正整数x，请你求出每个数的欧拉函数

欧拉函数：求出1~x中的与x互质的数的个数

互质：最大公约数为1的两个数：gcd(a,b)==1时，称a,b两数互质

原理：为链接处

[AcWing]873. 欧拉函数（C++实现）欧拉函数模板题_cloud的博客-CSDN博客_c++ 欧拉函数

#include
#include
using namespace std;int phi(int x)
{int res = x;for (int i = 2; i <= x / i; i++)//分解质因数常用模板{if (x % i == 0){res = res / i * (i - 1);//想干的操作：唯一不同的点while (x % i == 0) x /= i;}}if (x > 1) res = res / x * (x - 1);return res;
}int main()
{int n;cin >> n;while (n--){int x;cin >> x;cout << phi(x) << endl;}return 0;
}

筛法求欧拉函数

[AcWing]874. 筛法求欧拉函数（C++实现）线性筛过程中求欧拉函数模板题_cloud的博客-CSDN博客

#include
using namespace std;typedef long long LL;
const int N = 100010;
int primes[N];
int cnt;
int euler[N];//存放每个数i的欧拉数的个数
bool st[N];void get_eulers(int n)
{euler[1] = 1;for (int i = 2; i <= n; i++){if (!st[i]){primes[cnt++] = i;//线性筛euler[i] = i - 1;//第一种情况：i是n的一个质数:与它互质的数的个数为i-1个}for (int j = 0; primes[j] <= n / i; j++)//线性筛{int t = primes[j] * i;st[t] = true;//标记if (i % primes[j] == 0){//第二种情况：i%pj==0 :pj*i的欧拉数为pj乘上i的欧拉数euler[t] = euler[i] * primes[j];break;}euler[t] = euler[i] * (primes[j] - 1);}//第三种情况：i%pj!=0  pj*i的欧拉数为i的欧拉数乘以（pj-1）}
}int main()
{int n;cin >> n;get_eulers(n);LL res = 0;for (int i = 1; i <= n; i++) res += euler[i];cout << res << endl;return 0;
}

 费马定理

 快速幂

[AcWing]875. 快速幂（C++实现）快速幂模板题_cloud的博客-CSDN博客

#include 
#include using namespace std;typedef long long LL;LL qmi(int a, int b, int p)
{LL res = 1 % p;// 其实就是求k的二进制数，再用这二进制数求出a的k次方模p的结果while (b){// 如果当前k的末尾是1if (b & 1) res = res * a % p;// 组合求值a = a * (LL)a % p;// 向右移一位b >>= 1;}return res;
}int main()
{int n;scanf("%d", &n);while (n -- ){int a, b, p;scanf("%d%d%d", &a, &b, &p);printf("%lld\n", qmi(a, b, p));}return 0;
}

快速幂求逆元

[AcWing]876. 快速幂求逆元（C++实现）快速幂求逆元模板题_cloud的博客-CSDN博客

#include 
#include using namespace std;typedef long long LL;LL qmi(int a, int b, int p)
{LL res = 1;while (b){if (b & 1) res = res * a % p;a = a * (LL)a % p;b >>= 1;}return res;
}int main()
{int n;scanf("%d", &n);while (n -- ){int a, p;scanf("%d%d", &a, &p);if (a % p == 0) puts("impossible");else printf("%lld\n", qmi(a, p - 2, p));}return 0;
}

 扩展欧几里得算法

[AcWing]877. 扩展欧几里得算法（C++实现）扩展欧几里得算法模板题_cloud的博客-CSDN博客_扩展欧几里得算法c++

#include
#include
using namespace std;void exgcd(int a, int b, int& x, int& y)
{if (!b){x = 1, y = 0;return;}exgcd(b, a % b, y, x);y -= a / b * x;return;
}int main()
{int n;cin >> n;while (n--){int a, b;cin >> a >> b;int x, y;exgcd(a, b, x, y);printf("%d %d\n", x, y);}return 0;
}

 线性同余方程（拓展欧几里得的应用）

(拓展欧几里得+求余)acwing 878. 线性同余方程_岁忧的博客-CSDN博客

#include
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{//拓展欧几里得 if(!b){x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);//注意x和y交换一下位置y=y-a/b*x;return d;//返回最大公约数 
}
int main()
{int n;cin>>n;while(n--){int a,b,x,y;cin>>a>>b;exgcd(a,b,x,y);//用x，y的引用带回printf("%d %d\n",x,y); }
}

中国剩余定理(待回看)

中国剩余定理【数论】_100days-CSDN博客_中国剩余定理

#include
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll& x, ll& y) 
{if (!b){x = 1, y = 0;return a;}ll d = exgcd(b, a % b, y, x);y = y - a / b * x;return d;
}
int main()
{int n;cin >> n;ll a1, m1;cin >> a1 >> m1;bool flag = 1;for (int i = 0; i < n - 1; i++){ll a2, m2, k1, k2;cin >> a2 >> m2;ll d = exgcd(a1, -a2, k1, k2);if ((m2 - m1) % d) {flag = 0;break;}k1 = (k1 * (m2 - m1) / d) % abs(a2 / d);m1 = k1 * a1 + m1;a1 = abs(a1 / d * a2);//a1*a2/d是最小公倍数}if (flag) cout << (m1 % a1 + a1) % a1;//取余的技巧，为了得到一个正数else cout << -1;
}

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