第四讲 数学知识
一、数论
1.1、质数
const int N = 1e6+10;
int a[N];
//质数 使用 2 * i 来标记
void change()
{
int k;
for(int i=2;i<N;i++) a[i]=1;//是质数
for(int i=2;i<N;i++)
{
if(a[i]==1)
{
k=i+i;
while(k<=N)
{
a[k]=0;//不是质数
k+=i;
}
}
}
}
1.1.1、质数筛–埃氏筛法
埃氏筛法思想：质数的倍数就是合数，2 3 4 5 6 7 8 9 ,其中2是质数，那么 2*3=6 2*4=8 2*5=10 6、8、10都是合数，以此类推每当遇到一个质数就进行遍历，筛选掉其倍数合数。
const int N = 1000010;
int n;
int primes[N];
bool st[N];
void get_primes(int n){
for(int i = 2;i <= n; i++){
if(!st[i]){
primes[cnt++] = n;
for(int j = i + i;j <= n ;j += i){
st[j] = true;
}
}
}
}
int main(){
scanf("%d",&n);
get_primes(n);
cout << cnt << endl;
return 0;
}
1.1.2、质数筛–线性筛法
// 质数
// 线性筛法
/*
线性筛法 保证了 每一个合数都会被他的最小质因数筛选掉
*/
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 = 0;primes[j] <= n / i;j++){
st[primes[j] * i] = true; // 质数的倍数 *2 *3 *4...
if(i % primes[j] == 0)break; // primes[j] 一定是 i 的最小质因子
//这里的break 保证了只会被筛选一次
}
}
}
int main(){
int n ;
cin >> n;
get_primes(n);
cout << cnt << endl;
return 0;
}
1.2、分解质因数
/*
分解质因数
一个数n一定能分解为 它的 质因数的乘积
n = p1 ^ a1 * p2 ^ a2 ...
又由于最大质因数即>sqrt(n)的只有一个 ： 因为如果>sqrt(n)的有两个那么这两个数乘积就大于n
*/
int n;
void divide(int n){
for(int i = 2; i <= n / i;i++){ // 遍历到sqrt n 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("");
}
int main(){
scanf("%d",&n);
int a;
while(n--){
scanf("%d",&a);
divide(a);
}
return 0;
}
1.3、约数
1.3.1、试除法求约数
vector<int> get_divisors(int n){
vector<int> res;
for(int i = 1; i <= n / i; i++){ // sqrt范围
if(n % i == 0){
res.push_back(i); // i 是 n 的约数
if(i != n / i){
res.push_back(n / i); // 那么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 t : res)cout << t <<' ';
cout << endl;
}
return 0;
}
1.3.2、约数个数
typedef long long LL ;
const int mod = 1e9 + 7;
int main(){
int n;
cin >> n;
unordered_map<int,int> primes;
while(n--){
int a;
cin >> a;
for(int i = 2;i <= a / i;i++){
while(a % i == 0){
a /= i;
primes[i]++;
//primes里面 first就是底数 P second 就是指数 a
}
}
if(a > 1)primes[a]++;
}
LL res = 1;
// 约数个数 == (a1 + 1) * (a2 + 1) * (a3 + 1) *...*...
for(auto prime : primes) res = res * (prime.second + 1) % mod;
return 0;
}
1.3.3、约数之和
typedef long long LL ;
const int mod = 1e9 + 7;
int main(){
int n;
cin >> n;
unordered_map<int,int> primes;
while(n--){
int a;
cin >> a;
for(int i = 2;i <= a / i;i++){
while(a % i == 0){
a /= i;
primes[i]++;//质数的指数
}
}
if(a > 1)primes[a]++;
}
/*
primes里面 first就是底数 P second 就是指数 a
*/
LL res = 1;
for(auto prime : primes){
int p = prime.first, a = prime.second;
LL t = 1;
while(a--){
t = (t * p + 1) % mod; // (p^0 * p^1 * ... * p^a)
}
res = res * t % mod; // (p^0 * p^1 * ... * p^a) * (p1^0 * p1^1 * ... * p1^a) * ...
}
cout << res << endl;
return 0;
}
1.3.4、最大公约数–辗转相除法
int gcd(int a,int b){
return b ? gcd(b , a % b) : a;
}
int main(){
int n ;
scanf("%d",&n);
// while(n--){ // 方法一
// int a,b;
// cin >> a >> b;
//
// int res = __gcd(a,b);
//
// cout << res << endl;
// }
// 方法二
while(n--){
int a,b;
scanf("%d%d",&a,&b);
printf("%d\n",gcd(a,b));
}
return 0;
}
