数论 - 约数基础【试除法求所有约数 + 约数个数和约数之和 + 欧几里得算法-求解最大公约数】

拼搏现实的明天。 2021-07-25 00:09 403阅读 0赞

数论—约数基础

### **1.约数定义** ###

约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。在大学之前，"约数"一词所指的一般只限于正约数。约数和倍数都是二元关系的概念，不能孤立地说某个整数是约数或倍数。一个整数的约数是有限的。同时，它可以在特定情况下成为公约数。

### **2.试除法求所有约数** ###

vector<int> get_divisors(int x)
    { 
        vector<int> res;
        for (int i = 1; i <= x / i; i ++ )
            if (x % i == 0)
            { 
                res.push_back(i);
                if (i != x / i) res.push_back(x / i);
            }
        sort(res.begin(), res.end());
        return res;
    }

### **3.约数个数和约数之和** ###

理论：  
如果 N = p1^c1 \* p2^c2 \* … \*pk^ck  
约数个数： (c1 + 1) \* (c2 + 1) \* … \* (ck + 1)  
约数之和： (p1^0 + p1^1 + … + p1^c1) \* … \* (pk^0 + pk^1 + … + pk^ck)  
推导过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

### **4.欧几里得算法-求解最大公约数** ###

int gcd(int a,int b)
    { 
        return b ? gcd(b , a%b) : a;
    }

### **5.题目练习** ###

##### (1)AcWing-869. 试除法求约数 #####

给定n个正整数ai，对于每个整数ai,请你按照从小到大的顺序输出它的所有约数。  
**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个整数ai。  
**输出格式**  
输出共n行，其中第 i 行输出第 i 个整数ai的所有约数。  
**数据范围**  
1≤n≤100,  
2≤ai≤2∗109  
**输入样例：**  
2  
6  
8  
**输出样例：**  
1 2 3 6  
1 2 4 8  
**代码**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1e5 + 10;
    int ans[maxn],cnt;
    void get_divisors(int n)
    { 
    	for (int i = 1; i <= n / i; i++)   //只需遍历一半
    	{ 
    		if (n%i == 0)
    		{ 
    			ans[cnt++] = i;
    			if (i != n / i)
    			{ 
    				ans[cnt++] = n / i;
    			}
    		}
    	}
    	sort(ans,ans+cnt);
    }
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		cnt = 0;
    		int x;
    		cin >> x;
    		get_divisors(x);
    		for (int i = 0; i < cnt; i++)
    		{ 
    			cout << ans[i] << ' ';
    		}
    		cout << endl;
    	}
    	return 0;
    }

##### (2)AcWing -870. 约数个数 #####

给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对109+7取模。  
**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个整数ai。  
**输出格式**  
输出一个整数，表示所给正整数的乘积的约数个数，答案需对109+7取模。  
数据范围  
1≤n≤100,  
1≤ai≤2∗109  
**输入样例：**  
3  
2  
6  
8  
**输出样例：**  
12  
**代码**

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<unordered_map> //无序映射
    typedef long long ll;
    const int mod = 1e9 + 7;
    using namespace std;
    int main()
    { 
    	int n;
    	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)  //i为约数
    			{ 
    				x /= i;
    				primes[i]++;   //统计每个约数的个数
    			}
    		}
    		if (x > 1)  primes[x]++;  //如果还没分解清,说明剩下的这个数是它的因数且只有一个
    	}
    	ll ans = 1;
    	for (auto prime : primes)
    	{ 
    		ans = ans * (prime.second + 1) % mod;//约数个数=(a1+1)(a2+1)...(ak+1)
    	}
    	cout << ans << endl;
    	return 0;
    }

##### (3)AcWing- 871. 约数之和 #####

给定n个正整数ai，请你输出这些数的乘积的约数之和，答案对109+7取模。  
**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个整数ai。  
**输出格式**  
输出一个整数，表示所给正整数的乘积的约数之和，答案需对109+7取模。  
**数据范围**  
1≤n≤100,  
1≤ai≤2∗109  
**输入样例：**  
3  
2  
6  
8  
**输出样例：**  
252  
**代码**

#include<iostream>
    #include<algorithm>
    #include<unordered_map> //无序映射
    typedef long long ll;
    using namespace std;
    const int mod = 1e9 + 7;
    unordered_map<int, int >primes;
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		int x;
    		cin >> x;
    		for (int i = 2; i <= x / i; i++)
    		{ 
    			while (x%i == 0)  //i为约数
    			{ 
    				x /= i;
    				primes[i]++;  //统计每个约数的个数
    			}
    		}
    		if (x > 1) primes[x]++; //如果还没分解清,说明剩下的这个数是它的因数且只有一个
    	}
    	ll ans = 1;
    	for (auto prime : primes)
    	{ 
    		ll t = 1;
    		int p = prime.first, a = prime.second; //p为约数，a为约数的个数
    		while (a--)
    		{ 
    				t = (t*p + 1) % mod;//约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)
    		}
    		ans = (ans*t) % mod;
    	}
    	cout << ans << endl;
    	return 0;
    }

##### (4)AcWing -872. 最大公约数 #####

给定n对正整数ai,bi，请你求出每对数的最大公约数。  
**输入格式**  
第一行包含整数n。  
接下来n行，每行包含一个整数对ai,bi。  
**输出格式**  
输出共n行，每行输出一个整数对的最大公约数。  
**数据范围**  
1≤n≤105,  
1≤ai,bi≤2∗109  
**输入样例：**  
2  
3 6  
4 6  
**输出样例：**  
3  
2  
**代码**

#include<iostream>
    using namespace std;
    int gcd(int a, int b)
    { 
    	return b ? gcd(b, a%b) : a;  //(a,b)=(b,a%b)
    }
    int main()
    { 
    	int n;
    	cin >> n;
    	while (n--)
    	{ 
    		int a, b;
    		cin >> a >> b;
    		cout << gcd(a, b) << endl;
    	}
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/6714c7af093d4e8c996fa15d95b6bd54.png