目录
数论
一、质数
1）试除法判断质数
bool isPrime(int x)
{
if(x < 2) return false;
for(int i = 2;i<=x/i;i++)
if(x%i==0) return false;
return true;
}
2）分解质因数
void divide(int n)
{
for (int i = 2; i <= n / i; i ++ )
{
if( n % i == 0 )
{
int s = 0;
while (n % i == 0)
{
n /= i;
s++;
}
printf("%d %d\n",i,s);
}
}
if (n > 1) printf("%d %d\n",n,1);
puts("");
}
3）筛质数
1、普通筛质数
void getPrimes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i])
{
primes[cnt ++] = i;
}
for (int j = i + i; j <= n; j ++) st[j] = true;
}
}
2、埃氏筛质数
void getPrimes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!st[i])
{
primes[cnt ++] = i;
for (int j = i + i; j <= n; j ++) st[j] = true; //只对质数的倍数筛掉
}
}
}
3、欧拉筛
void getPrimes(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; //primes[j]是i的最小质因子，我们只用最小质因子来筛，所以遇到了就break
}
}
}
二、约数
1）试除法求约数
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> gcd(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);
}
}
sort(res.begin(),res.end());
return res;
}
int main()
{
scanf("%d", &n);
while (n --)
{
int x;
scanf("%d", &x);
auto res = gcd(x);
for(auto item:res) printf("%d ", item);
puts("");
}
return 0;
}
2）求n个数的积对常数取模的结果
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e9+7;
int n;
int main()
{
cin >> n;
ll res = 1;
unordered_map<int,int> 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] ++ ;
}
//至此，我们就把最后的乘积的每个质因子的指数都求出来了，根据公式得出约数个数是(a1+1)*(a2+1)……*(ak+1);
for (auto item : primes) res = res * (item.second + 1) % N;
printf("%lld", res);
return 0;
}
3）求n个数的积的约数个数
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod = 1e9 +7;
int n;
int main()
{
cin>>n;
unordered_map<int,int> 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 prime:primes)
{
int p = prime.first, a = prime.second;
ll t = 1;
while (a -- ) t = (t * p + 1) % mod;
res = res * t % mod;
}
cout<<res;
return 0;
}
4）求最大公约数
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
三、欧拉函数
欧拉函数的证明
1）欧拉函数
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
while (n --)
{
int a;
cin >> a;
int res = a; // res存储最终的结果
for (int i = 2; i <= a / i; i ++) // 对数据先进行质因数分解
{
if(a % i == 0) // i是a的一个约数
{
res = res / i * (i - 1); // 化简之后的，相当于乘以 1-(1/i)
while (a % i == 0) a /= i;
}
}
if(a > 1) res = res / a * (a - 1);
cout << res <<endl;
}
return 0;
}
2）筛法求欧拉函数
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
int primes[N],cnt;
ll phi[N]; // 欧拉函数
bool st[N]; // 标记是否是质数
ll get_Olers(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if(!st[i])
{
primes[cnt ++ ] = i;
phi[i] = i-1; // i是质数，1~i-1都与它互质
}
for(int j = 0; primes[j] <= n / i; j ++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0)
{
phi[primes[j] * i] = phi[i] * primes[j];
break;
}
//如果primes[j]不是i的质因子，那么phi[primes[j]*i] = phi[i] * primes[j] * (1-1/primes[j]),化简得到如下代码
phi[primes[j] * i] = phi[i] * (primes[j] - 1);
}
}
ll res = 0;
for(int i = 1; i <= n; i ++) res += phi[i];
return res;
}
int main()
{
int n;
cin >> n;
cout << get_Olers(n) << endl;
return 0;
}
四、快速幂
欧拉定理
快速幂
#include <iostream>
using namespace std;
typedef long long ll;
ll qmi(ll a, ll k, ll p)
{
ll res = 1;
while (k)
{
if (k & 1) res = res * a % p;
k = k >> 1;
a = a * a % p;
}
return res;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
ll a,k,p;
scanf("%lld%lld%lld",&a,&k,&p);
printf("%lld\n",qmi(a,k,p));
}
return 0;
}
快速幂求逆元
#include <iostream>
using namespace std;
typedef long long ll;
ll qmi(ll a, ll k, ll p)
{
ll res = 1;
while (k)
{
if (k & 1) res = res * a % p;
k = k >> 1;
a = a * a % p;
}
return res;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
ll a,p;
scanf("%lld%lld",&a,&p);
ll res = qmi(a,p-2,p);
if (a % p) printf("%lld\n",res);
else puts("impossible");
}
return 0;
}
五、扩展欧几里得算法
裴属定理
扩展欧几里得算法（求ax + by = gcd(a,b) 中的x和y的算法）
#include <iostream>
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);
y -= a / b * x;
return d;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int a,b,x,y;
scanf("%d%d",&a, &b);
exgcd(a,b,x,y);
printf("%d %d\n",x,y);
}
return 0;
}
线性同余方程（求 ax % m = b 式子中的x,给定a,b,m）
#include <iostream>
using namespace std;
typedef long long ll;
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);
y -= a/b*x;
return d;
}
int main()
{
int n;
cin >> n;
while (n -- )
{
int a,b,m;
scanf("%d%d%d",&a,&b,&m);
int x,y;
int d = exgcd(a,m,x,y);
if (b % d) puts("impossible");
else printf("%d\n",(ll)x * b / d % m);
}
return 0;
}
六、中国剩余定理
题目：
给定 2n2
标签：return,数论,res,ll,cin,int,include From： https://www.cnblogs.com/zj-cnbolgs/p/18566153