数论基础
数论
线性筛素数
洛谷P3383 【模板】线性筛素数
数据范围：n=10^8，找出第k 小的质数
欧拉线性筛的关键在于：每个合数只被它最大的非自身的因数筛掉：最大的非自身的因数*最小质因子=这个数
例如：12不会被4筛掉，而是被6筛掉；45不会被9筛掉，而是被15筛掉。
i的最小质因子一定是prime[j]，因为如果小于j，一定会在更早被枚举到时一定会break掉，就不存在现在这一步
i*prime[j]的最小质因子也是prime[j]，与上一步同理
（对break情况的进一步说明）当出现i的最小质因子prime[j]时，
我们就知道n*prime[j]（n>i） 的形式一定会在后面再次出现，也就是说这个数的最大因数还没有出现，我们留到后面再把他筛掉，及时break掉保证每个数只被筛一次
通俗易懂的举例：以12为例，2,3,4,6都可筛掉12
i=2：2 * 2=4 break; i=3 3 * 2=6, 3 * 3=9 break;
i=4: 4 * 2 =8 break; i=5 5 * 2=10, 5 * 3=15; 5 * 5=25 break;
i=6: 6 * 2=12 break;实现了在12的最大因数6 才将12筛掉
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e8+5;
int a[N],prime[N/3];
int cnt=0;
int n,q,op;
void init()
{
for(int i=2;i<=n;i++)
{
if(!a[i])prime[++cnt]=i;
for(int j=1;i*prime[j]<=n and j<=cnt;j++)
{
a[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>q;
init();
while(q--)
{
cin>>op;
cout<<prime[op]<<endl;
}
return 0;
}
|
求约数个数
acwing 870
给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对10^9+7取模。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对10^9+7取模。
数据范围
1≤n≤100
1≤ai≤2∗10^9
输入样例：
输出样例：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<unordered_map>
using namespace std;
const int m=1e9+7;
int n,x;
int a[10050];
int cnt=0;
int main()
{
cin>>n;
unordered_map<int,int> prime;
while(n--)
{
cin>>x;
for(int i=2;i<=x/i;i++)
{
while(x%i==0)
{
x/=i;
prime[i]++;
}
}
if(x>1)prime[x]++;
}
long long res=1;
for(auto i:prime)
{
res=res*(i.second+1)%m;
}
cout<<res;
return 0;
}
|
求约数之和
acwing 871
给定n个正整数ai，请你输出这些数的乘积的约数之和，答案对10^9+7取模。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对10^9+7取模。
数据范围
1≤n≤100,
1≤ai≤2∗10^9
输入样例：
输出样例：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<unordered_map>
using namespace std;
const int m=1e9+7;
int n,x;
int a[10050];
int cnt=0;
int main()
{
cin>>n;
unordered_map<int,int> prime;
while(n--)
{
cin>>x;
for(int i=2;i<=x/i;i++)
{
while(x%i==0)
{
x/=i;
prime[i]++;
}
}
if(x>1)prime[x]++;
}
long long res=1;
for(auto i:prime)
{
int p=i.first,a=i.second;
long long t=1;
while(a--)
{
t=(t*p+1)%m;
}
res=res*t%m;
}
cout<<res;
return 0;
}
|
最大公约数
欧几里得算法：辗转相除法
d|a and d|b —-> d|ax+by
gcd(a,b)=gcd(b,a-c*b)=gcd(b,a%b);
代码：
1
2
3
4
| int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
|
欧拉函数
定义
在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）
算数基本定理
算术基本定理又叫唯一分解定理，可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1^a1^ P2^a2^P3^a3^……Pn^an^，这里P1<P2<P3……<Pn均为质数，其中指数ai是正整数。
acwing873 欧拉函数
给定n个正整数ai，请你求出每个数的欧拉函数。
1≤n≤100,
1≤ai≤2∗10^9
输入样例：
输出样例：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
int main()
{
cin>>n;
while(n--)
{
int x;
cin>>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);
cout<<res<<endl;
}
return 0;
}
|
acwing874 筛法求欧拉函数
给定一个正整数n，求1~n中每个数的欧拉函数之和。1≤n≤10^6
解析：欧拉函数的筛法是线性筛素数的加强版
第一种解释：
要想求欧拉函数需要用到以下几个性质( p为素数 )：
phi(p) == p-1 因为素数p除了1以外的因子只有p，所以与 p 互素的个数是 p - 1个
phi(p^k) == p^k - p^(k-1) == (p-1) * p^(k-1)
证明：
令n == p^k,小于 n 的正整数共有 p^k-1 个,其中与 p 不互素的个数共 p^(k-1)-1 个，它们是 1p,2p,3*p … (p^(k-1)-1)*p
所以phi(p^k) == (p^k-1) - (p^(k-1)-1) == p^k - p^(k-1) == (p-1) * p^(k-1)。
如果i mod p == 0, 那么 phi(i * p) == p * phi(i) （证明略）
举个例子：
假设 p = 3,i = 6,p * i = 18 = 2 * 3^2;
phi(3 * 6) == 18*(1-1/2)*(1-1/3) = 6
p * phi(i) = 3 * phi(6) = 3 * 6 * (1-1/2) * (1-1/3) = 6 = phi(i * p) 正确
如果i mod p != 0, 那么 phi(i * p) == phi(i) * (p-1)
证明：
i mod p 不为0且p为质数, 所以i与p互质, 那么根据积性函数的性质 phi(i * p) == phi(i) * phi(p) 其中phi(p) == p-1
所以 phi(i * p) == phi(i) * (p-1).
再举个例子：
假设i = 4, p = 3, i * p = 3 * 4 = 12
phi(12) = 12 * (1-1/2) * (1-1/3) = 4
phi(i) * (p-1) = phi(4) * (3-1) = 4 * (1-1/2) * 2 = 4 = phi(i * p)正确
第二种解释：
phi[prime[j] * i]分为两种情况：
- i % prime[j] == 0时：primes[j]是i的最小质因子，也是prime[j] * i的最小质因子，因此1 - 1 / prime[j]这一项在phi[i]中计算过了，只需将基数N修正为prime[j]倍，最终结果为phi[i] * prime[j]。
- i % primes[j] != 0时：primes[j]不是i的质因子，只是prime[j] * i的最小质因子，因此不仅需要将基数N修正为prime[j]倍，还需要补上1 - 1 / prime[j]这一项，因此最终结果phi[i] * (prime[j] - 1)。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=1e6+5;
int a[N],prime[N/3];
int phi[N];
long long tot=0,cnt=0;
int n,q,op;
void init()
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!a[i])
{
prime[++cnt]=i;
phi[i]=i-1;
}
for(int j=1;i*prime[j]<=n and j<=cnt;j++)
{
a[i*prime[j]]=1;
if(i%prime[j]==0)
{
phi[prime[j]*i]=phi[i]*prime[j];
break;
}
phi[prime[j]*i]=phi[i]*(prime[j]-1);
}
}
for(int i=1;i<=n;i++)
{
tot+=phi[i];
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
init();
cout<<tot;
return 0;
}
|
欧拉定理
内容：
若a与n互质，则有a^phi(n) ≡ 1（mod p）。
证明：
费马小定理（欧拉定理的特例）：
如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。
快速幂
基于 二进制 位运算 来实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll qpow(ll a,ll b,ll p)
{
ll res=1;
while(b)
{
if(b&1)
{
res=res*a%p;
}
a=a*a%p;
b>>=1;
}
return res%p;
}
int main()
{
ios::sync_with_stdio(0);
int n;
ll a,b,p;
cin>>n;
while(n--)
{
cin>>a>>b>>p;
cout<<qpow(a,b,p)<<endl;
}
return 0;
}
|
乘法逆元
参考：https://www.cnblogs.com/zjp-shadow/p/7773566.html
逆元的定义
求法总结
- 拓展欧几里得：解线性同余方程，不要求模数为质数
- 快速幂：费马小定理，要求模数为质数
- 线性求逆元，求一连串数字对一个质数p的逆元，线性递推，要求模数为质数
快速幂求逆元
原理：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll qpow(ll a,ll b,ll p)
{
ll res=1;
while(b)
{
if(b&1)
{
res=res*a%p;
}
a=a*a%p;
b>>=1;
}
return res%p;
}
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
ios::sync_with_stdio(0);
int n;
ll a,b,p;
cin>>n;
while(n--)
{
cin>>a>>p;
ll res=qpow(a,p-2,p);
if(gcd(a,p)==1)cout<<res<<endl;
else cout<<"impossible"<<endl;
}
return 0;
}
|
扩展欧几里得算法
引理：裴蜀定理
若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。
它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1
一些自己的理解：
a*x mod n==1 <=> (ax-1)整除n <=> 令y=-(ax-1)/n
<=> ax-ny==1 目标转化为求方程的解x,y（x的解为x0+kn）
求方程的解：ax+by=c,c一定是gcd(a,b)的倍数,否则无整数解 (裴蜀定理)
ax+by=gcd(a,b)=1 –> 联想到gcd(a,b)的求法：gcd(a,b)=gcd(b,a%b); （1式）
有:bx1+(a%b)y1=gcd(b,a%b)=1 （2式）
由 1式==2式 –> ax+by=bx1+(a-(a/b))y1
–> ax+by=ay1+b(x1-(a/b)y1)
–>x=y1,y=x1-(a/b)y1 得到递推关系，可以设计递归函数
求x,y转化为求x1,y1
——why? ——由gcd(a,b)的边界条件为 b=0 可知递归边界一定是 ax+0y==gcd(a,0), 随便给一组合法解为x=1,y=0
从上往下推：求gcd ; 从下往上推：求最初二元一次不定方程的解！
扩欧求乘法逆元代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
using namespace std;
ll x,y;
void exgcd(ll a,ll b)
{
if(b==0)
{
x=1,y=0;
return ;
}
exgcd(b,a%b);
ll x0=x,y0=y;
x=y0;
y=x0-(a/b)*y0;
return ;
}
int main()
{
ll a,n;
while(cin>>a>>n)
{
if(a==0 and n==0)break;
exgcd(a,n);
while(x<0)
{
x+=n;
}
x%=n;
cout<<x<<endl;
}
return 0;
}
|
acwing877 扩展欧几里得算法
给定n对正整数ai,bi，对于每对数，求出一组xi,yi，使其满足ai∗xi+bi∗yi=gcd(ai,bi)。本题答案不唯一，输出任意满足条件的xi,yi均可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
int n;
ll x,y;
void exgcd(ll a,ll b)
{
if(b==0)
{
x=1,y=0;
return ;
}
exgcd(b,a%b);
ll x1=x,y1=y;
x=y1;
y=x1-y1*(a/b);
return ;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
ll a,b;
while(n--)
{
cin>>a>>b;
exgcd(a,b);
cout<<x<<" "<<y<<endl;
}
return 0;
}
|
acwing878 线性同余方程
给定n组数据ai,bi,mi，对于每组数求出一个xi，使其满足ai∗xi≡bi(mod mi)，如果无解则输出impossible。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
int n;
ll x,y;
ll d;
void exgcd(ll a,ll b)
{
if(b==0)
{
x=1,y=0;
return ;
}
exgcd(b,a%b);
ll x1=x,y1=y;
x=y1;
y=x1-y1*(a/b);
return ;
}
ll gcd(ll a,ll b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
ll a,b,m;
while(n--)
{
cin>>a>>b>>m;
d=gcd(a,m);
if(b%d==0)
{
exgcd(a,m);
cout<<x*(b/d)%m<<endl;
}
else cout<<"impossible"<<endl;
}
return 0;
}
|
中国剩余定理
内容
