数论
s_computer · · 个人记录
质数
定义：在大于1的整数中，因数只包含1和本身的数叫质数
判质数
1.试除法
最朴素的做法：直接暴力循环
//判断n是否是质数
int flag=1;
for(int i=2;i<n;i++)
{
if(n%i==0)
{
flag=0;
break;
}
}
if(flag) printf("yes");
else printf("no");优化：因数是成对出现的，所以循环到i i < n即可，但是i>=1e5的时候，i i就有溢出风险，所以我们用 i<n/i 作为判断条件，这样绝对不hi溢出。
代码：
for(int i=2;i<=n/i;i++)
{
if(n%i==0)
{
flag=0;
break;
}
}
if(flag) printf("yes");
else printf("no");2.分解质因数
朴素思路：循环，当遇上可以被n整除的数的时候，就用n不断的除掉它，然后记录除的次数即可。
代码：
for(int i=2;i<=n;i++)
{
int s=0;
while(n%i==0)
{
s++;
n /= i;
}
printf("%d %d",i,s);
}优化：有一个定理，数n最多有一个大于更号n的质因数，所以可以简化我们的循环
for(int i=2;i<n/i;i++)
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
printf("%d %d",i,s);
}
if(n) printf("%d 1",n);筛法求质数
思路：循环，对于每一个访问到的数，删掉它的整数倍，最后剩下的数就是质数
代码：
int st[];
vector<int>p;
for(int i=2;i<=n;i++)
{
if(!st[i]) p.push_back(i);
for(int j=i+1;j<=n;j+=i) st[j]=1;
}优化：不用删除所有数的整数倍，只用删掉质数的整数倍即可。（埃氏筛法） 时间复杂度O(nloglogn) 代码：
int st[];
vector<int>p;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
p.push_back(i);
for(int j=i+1;j<=n;j+=i) st[j]=1;
}
}质数定理：1到n当中有(n/ln(n))个质数
线性筛法：原理一个合数有且只有一个最小质因数，我们就用这个最小质因数来筛掉它，这样就能保证每个数只被筛一次，就满足了线性的要求
for(int i=2;i<=n;i++)
{
if(!st[i]) p.push_back(i);
for(auto t:p)
{
if(t>n/i) break; //用t*i来筛数，所以要满足这个条件，否则得到的数就要超过n的范围
st[t*i]++;
if(i%t==0) break;
//如果t比i的最小质因数还大，那么例如i=4,t=3,那么12就会被筛掉，但实际上i=6,t=2时12会被筛掉，这样12就被筛了两次，不符合线性
//这种算法的原理是一个数只会被它的最小质因数筛掉，一个合数一定有且仅有最小质因数，这样每个数只被筛一次，就符合线性的要求
}
}约数
1.求一个数的所有约数 就用试除法，循环来实现，优化就是i<=n/i
for(int i=1;i<=n/i;i++)
{
if(n%i==0)
{
p.push_back(i);
if(n/i!=i) push_back(n/i);
}
}2.求约数个数（int范围内，约数最多的一个数有1500个约数） 原理：利用分解质因数的原理来考虑，N=a1^k1 a2^k2 ... an^kn 约数的个数cnt=(k1+1) (k2+1) ... (kn+1)//就是选几个的问题
3.求约数的和 原理：跟求约数的个数的原理类似，不过求解的式子有变化(a1^0+a1^1+...+a1^k1)(...)(an^0+an^1+...+an^kn),将式子展开就能得到每个约数相加（对于每个括号内的可以用秦九韶来优化）
4.求两个数的最大公约数（辗转相除法）（对于多个数就两两求） 时间复杂度O(logn) gcd(a,b)=gcd(b,a mod b)
欧拉函数
欧拉函数：1-n中，与n互质（两个数的最大公约数是1）的数的个数 公式：f(n)=n(1-1/a1)(1-1/a2)...(1-1/an)(a是n的质因数) 计算原理是容斥原理：
给定n个数，求每个数的欧拉函数，时间复杂度O(n * sqrt(ai))
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a;
scanf("%d",&a);
int res=a;
for(int i=2;i<=a/i;i++)
{
if(a%i==0)
{
res=res/i*(i-1);//如果先乘可能会爆int
while(a%i==0) a /= i;
}
}
if(a>1) res = res/a*(a-1);
printf("%d\n",res);
}
}筛法求欧拉函数
这里我们求的是1-n中每个数欧拉函数个数的和，求每个数的欧拉函数时，我们用到了线性筛法的原理 先来看线性筛法的模板
for(int i=2;i<=n;i++)
{
if(!st[i]) p.push_back(i);
for(auto t:p)
{
if(t>n/i) break;
st[i*t]++;
if(i%t==0) break;//t再大就不能控制t是将要筛掉的数的最小质因数了，也就不能保证算法是线性的了
}
}在式子中，我们想要求每个数的欧拉函数，可发现每次循环最多可以访问到3类数， 第一类数：质数，质数p的欧拉函数是[1,p-1]；
第二类数，合数：合数又分两种：
一种是i%t==0时的合数： t * i的质因子由t的质因子和i的质因子构成，t的质因子只有本身，i%t==0时，我们考虑i的质因数就已经把t考虑进去了，所以：
另一种是i%t!=0时的合数： 同样t * i的质因子是由t的质因子和i的质因子构成的，t的质因子只有本身，这里t不是i的质因子，所以要额外增加一个t，即：
那么对于每次循环能访问到的数，我们就将其欧拉函数算出来了，按照线性筛法的原理，我们这里的计算也是线性的。代码如下：
#include<bits/stdc++.h>
using namespace std;
int st[1000010],o[1000010];
vector<int>p;
int main()
{
int n;
scanf("%d",&n);
o[1]=1;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
p.push_back(i);
o[i]=i-1;
}
for(auto t:p)
{
if(t>n/i) break;
st[i*t]++;
if(i%t==0)
{
o[i*t]=t*o[i];
break;
}
else
{
o[i*t]=o[i]*(t-1);
}
}
}
long long res=0;
for(int i=1;i<=n;i++) res += o[i];
cout<<res;
}欧拉定理、费马小定理及证明：
快速幂
求a的b次方mod p的结果。
#include<bits/stdc++.h>
using namespace std;
int qmi(int a,int b,int p)
{
int res=1;
while(b)
{
if(b&1) res = (long long)res*a%p;
b >>= 1;
a = (long long)a*a%p;
}
return res;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a,b,p;
scanf("%d%d%d",&a,&b,&p);
cout<<qmi(a,b,p)<<endl;
}
}res = (long long)res * a%p;先将res转成longlong类型，然后再乘上a,防止溢出，但是右边计算后的结果是int范围内的，再将它赋值给int是没有影响的