模板:
//质数判定--试除法
//朴素 O(N)
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;
}
//朴素优化 O(sqrt(N))
bool is_prime(int n)
{
if(n<2)return false;
for(int i=2;i<=n/i;i++)//不推荐写sqrt(N)，每次循环都会执行sqrt，比较慢
//也不推荐i*i<=n，当i较大时,存在溢出风险，变成负数
{
if(n%i==0)return false;
}
return true;
}
//分解质因数--试除法
//原理:算数基本定理:一个数由多个质数的乘积组成
//从小到大枚举所有数,包括合数和质数，去判断是否是n的约数
//时间复杂度,最好情况：当数据量N=2^K,由于i从2开始，那么一开始就会除k次2,最后n=1，那么就是O(logn)
//最坏就是 枚举完，O(sqrt(n))
void divide(int n)
{
//n中最多只包含一个大于sqrt(n)的质数
//其他的质因子必定小于sqrt(n) ,故可以i<=n/i
//先枚举小于sqrt(n)的数，除干净后，剩下的数就是大于sqrt(n)的质因子
for(int i=2;i<=n/i;i++)
{
if(n%i==0)//n是i的倍数，且2~i-1之间不存在n的因子
//但是i却可以整除n，因此此时i一定是质数
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
cout << i << ' ' << s << endl;
}
}
//剩余的数大于1，那么这个数就是大于sqrt(n)的唯一的质因数
if( n > 1)cout << n << 1 << endl;
}
//筛法
//朴素 O(nlogn)
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2开始枚举
{
if(st[i]==false)//找到素数,就加入primes中
{
primes[cnt++]=i;
}
//无论是不是素数都将其倍数都筛掉
for(int j=i+i;j<=n;j+=i)st[j]=true;
}
}
//埃氏筛法
//筛法O(nloglogn),或者粗略的认为O(n)
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2开始枚举
{
if(st[i]==false)//找到素数,就加入primes中
{
primes[cnt++]=i;
//将质数其倍数都筛掉,因为质数的倍数必定是合数,因此可以放在判断里面
//算数基本定理:合数能通过比他小的质数表示出来
for(int j=i+i;j<=n;j+=i)st[j]=true;
}
}
}
//线性筛法
//1e6的数据和埃筛效率差不多,1e7比埃筛快一倍
//n只会被n的最小质因子筛掉
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2开始枚举所有数
{
//找到素数,就加入primes中
if(st[i]==false)primes[cnt++]=i;
//从小到大枚举所有质数
for(int j = 0; primes[j] <= n / i;j ++ )//也可以primes[j]*i<=n,表示枚举所有以primes[j]为最小质因子的数
{
st[primes[j]*i]=true;//每次把质数和i的乘积筛掉
if(i % primes[j]==0)break; //primes[j]一定是i的最小质因子
//因为primes[j]是从小到大枚举的,那么一旦primes[j]可以整除i,它就是最小的质因数
//因此primes[j]一定是primes[j]*i最小质因子
}
//核心:每一个数,不管是合数还是质数,都只会被它的最小质因子筛唯一一次,所以是线性的
}
}
//求约数--试除法
//朴素->优化 O(sqrt(n))
vector<int> get_divisors(int n)
{
vector<int> res;
for(int i=1;i<=n/i;i++)//朴素就是i<n
{
if(n%i==0)
{
res.push_back(i);
//i为约数,那么n/i也是n的约数
if(i != n/i )res.push_back(n/i);//有可能n=i*i,为了防止重复就得判断
}
}
sort(res.gegin(),res.end());
return res;
} 试除法求质数
https://www.acwing.com/problem/content/description/868/
#include<iostream>
using namespace std;
long long a;
int n;
bool is_prime(int n)
{
if(n<2)return false;
for(int i=2;i<=n/i;i++)//不推荐写sqrt(N)，每次循环都会执行sqrt，比较慢
//也不推荐i*i<=n，当i较大时,存在溢出风险，变成负数
{
if(n%i==0)return false;
}
return true;
}
int main()
{
cin >> n;
while(n--)
{
cin >> a;
if(is_prime(a))cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}分解质因数:
https://www.acwing.com/problem/content/869/
#include<iostream>
using namespace std;
int m;
int a;
void divide(int n)
{
//n中最多只包含一个大于sqrt(n)的质数
//其他的质因子必定小于sqrt(n) ,故可以i<=n/i
for(int i=2;i<=n/i;i++)
{
if(n%i==0)//n是i的倍数，且2~i-1之间不存在n的因子
//但是i却可以整除n，因此此时i一定是质数
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
cout << i << ' ' << s << endl;
}
}
if( n > 1)cout << n << ' ' << 1 << endl;
cout << endl;
}
int main()
{
cin >> m;
while(m--)
{
cin >> a;
divide(a);
}
return 0;
}筛质数:
https://www.acwing.com/problem/content/description/870/
朴素:
#include<iostream>
using namespace std;
const int N = 1e6+10;
int num;
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2开始枚举
{
if(st[i]==false)//找到素数,就加入primes中
{
primes[cnt++]=i;
}
//无论是不是素数都将其倍数都筛掉
for(int j=i+i;j<=n;j+=i)st[j]=true;
}
}
int main()
{
cin >> num;
get_primes(num);
cout << cnt << endl;
}埃筛优化:
埃筛会重复筛一些数
#include<iostream>
using namespace std;
const int N = 1e6+10;
int num;
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2开始枚举
{
if(st[i]==false)//找到素数,就加入primes中
{
primes[cnt++]=i;
//将质数其倍数都筛掉,因为质数的倍数必定是合数
//算数基本定理:合数能通过比他小的质数表示出来
for(int j=i+i;j<=n;j+=i)st[j]=true;
}
}
}
int main()
{
cin >> num;
get_primes(num);
cout << cnt << endl;
}线性筛:
#include<iostream>
using namespace std;
const int N = 1e6+10;
int num;
int primes[N],cnt;
bool st[N];
void get_primes(int n)
{
for(int i=2;i<=n;i++)//从2开始枚举所有数
{
//找到素数,就加入primes中
if(st[i]==false)primes[cnt++]=i;
//从小到大枚举所有质数
for(int j = 0; primes[j] <= n / i;j ++ )//也可以primes[j]*i<=n,表示枚举所有以primes[j]为最小质因子的数
{
st[primes[j]*i]=true;//每次把质数和i的乘积筛掉
if(i % primes[j]==0)break; //primes[j]一定是i的最小质因子
//因为primes[j]是从小到大枚举的,那么一旦primes[j]可以整除i,它就是最小的质因数
//因此primes[j]一定是primes[j]*i最小质因子
}
//每一个数,不管是合数还是质数,都只会被它的最小质因子筛唯一一次,所以是线性的
}
}
int main()
{
cin >> num;
get_primes(num);
cout << cnt << endl;
}求约数--试除法
https://www.acwing.com/problem/content/871/
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,a;
vector<int> get_divisors(int n)
{
vector<int> res;
for(int i=1;i<=n/i;i++)//朴素就是i<n
{
if(n%i==0)
{
res.push_back(i);
if(i != n/i )res.push_back(n/i);//有可能n=i*i,为了防止重复就得判断
}
}
sort(res.begin(),res.end());
return res;
}
int main()
{
cin >> n;
while(n--)
{
cin >> a;
vector<int>res = get_divisors(a);
for(auto i:res)
cout << i << ' ';
cout << endl;
}
}
求约数个数
https://www.acwing.com/problem/content/872/
对于数N,根据算数基本定理可以分解为d这样的形式的若干数相乘
N的任何一个约数都长成d这样的形式,其中每一个d的p的指数都不同,那么其约数d值也就不同,算数基本定理可以得到每个数的因式分解是不同的,因式分解不一样,两个数的值就不一样
pi的指数有α+1种选法,根据排列组合,总共有(α1+1)*(α2+1)*(α3+1)*.......(αk+1)种选法,即为N的约数的个数
#include<iostream>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL res=1;
int x,n;
int main()
{
unordered_map<int,int> primes;
cin >> n;
while(n--)
{
cin >> x;
//首先先分解质因数
for(int i=2;i<=x/i;i++)
{
while(x % i == 0)
{
x /= i;
primes[i]++;//把所有质因子的指数累加起来
}
}
if(x>1)primes[x]++;//大于sqrt(x)的质因子
}
for(auto prime:primes)res=res*(prime.second+1) % mod;
cout << res << endl;
}求约数之和
https://www.acwing.com/problem/content/873/
把约数之和的式子展开,就有许多的扩号这样的形式
每一个括号里都是p1^β1*p2^β2...pk^βk的形式,且每一个括号里面形式都不一样
根据算数基本定理,这样的形式,每一个括号,实际上都是一个约数
那么这么多括号之和就是约数的和
#include<iostream>
#include<cmath>
#include<unordered_map>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL res=1;
int x,n;
int main()
{
unordered_map<int,int> primes;
cin >> n;
while(n--)
{
cin >> x;
for(int i=2;i<=x/i;i++)
{
while(x % i == 0)
{
x /= i;
primes[i]++;//把所有质因子的指数累加起来
}
}
if(x>1)primes[x]++;//大于sqrt(x)的质因子
}
for(auto prime:primes)
{
int p = prime.first;
int a = prime.second;
LL t = 1;
while(a--)t = (t*p+1) % mod;//令t=pt+1,执行2次,那么t = p^2+p+1,执行a次就有p^a+p^a-1+,,,+p^0
res=res*t%mod;
}
cout << res << endl;
}欧几里得算法(辗转相除法)
有一个性质:a是d的约数,b也是d的约数,那么有x倍的a+y倍的b为d的约数,x,y为任意
可以证明a,b的最大公约数是b,a mod b的最大公约数,反之也成立
https://www.acwing.com/problem/content/874/
#include<iostream>
using namespace std;
const int N = 1e5+10;
int x,y,n;
int gcd(int a,int b)
{
return b ? gcd(b,a%b):a;
}
int main()
{
cin >> n;
for(int i=0;i<n;i++)
{
cin >> x >> y;
cout << gcd(x,y) << endl;
}
return 0;
}