数论----约数-Toy模板网

这篇具有很好参考价值的文章主要介绍了数论----约数。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一，写出一个数的所有约数

活动 - AcWing

思想：这题数据较大，使用试除法来减小时间复杂度。还有一点需要注意，两约数相同，只保留一个。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;

//试除法
void f(int num, vector<int> &v) {
	for (int i = 1; i <= sqrt(num);i++) {
		if (num % i == 0) {
			v.push_back(i);
			if(i!=num/i) v.push_back(num / i);//注意，只有两者不相同时才能进数组
		}
	}
	sort(v.begin(), v.end());
	return;
}

int main()
{
	int T;
	cin >> T;
	while (T--) {
		int num;
		vector<int> v;
		cin >> num;
		f(num, v);
		for (int i = 0; i < v.size(); i++) {
			cout << v[i];
			if (i != v.size() - 1) cout << " ";
		}
		cout << endl;
	}
	return 0;
}

二，求约数个数

思想：这题数据很大，需要使用特殊的方法，这篇题解写的很详细

（AcWing 870. 约数个数---$\color{red}{海绵宝宝来喽}$ - AcWing）

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
const long long mod = 1e9 + 7;



int main()
{
	int n;
	cin >> n;
	map<long long, int> mp;
	while (n--) {
		long long num;
		cin >> num;
		for (int i = 2; i <= sqrt(num); i++) {//求每一项的指数
			while (num % i == 0) {
				mp[i]++;
				num /= i;
			}
		}
		//如果有剩余，也是一个质因子
		if (num > 1) mp[num]++;
	}
	
	long long ans = 1;
	for (auto it = mp.begin(); it != mp.end(); it++) {
		//套用公式(x1+1)(x2+1)(x3+1)…(xk+1)
		ans = ans * (it->second + 1) % mod;
	}
	cout << ans << endl;
	return 0;
}

三，约数之和

活动 - AcWing

思想：

基本思想：
如果 N=p1c1∗p2c2∗…∗pkck
约数个数：(c1+1)∗(c2+1)∗…∗(ck+1)
约数之和： (p10+p11+…+p1c1)∗…∗(pk0+pk1+…+pkck)

根据上面的公式，我们在上一题的基础上进行修改就可以了

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
const long long mod = 1e9 + 7;

int main()
{
	int n;
	cin >> n;
	map<long long, int> mp;
	while (n--) {
		long long num;
		cin >> num;
		for (int i = 2; i <= sqrt(num); i++) {//求每一项的指数
			while (num % i == 0) {
				mp[i]++;
				num /= i;
			}
		}
		//如果有剩余，也是一个质因子
		if (num > 1) mp[num]++;
	}
	
	long long ans = 1;
	for (auto it = mp.begin(); it != mp.end(); it++) {
		//套用公式(p10+p11+…+p1c1)∗…∗(pk0+pk1+…+pkck)
		long long a = it->first, b = it->second;
		long long t = 1;
		while (b--) t = (t * a + 1) % mod;
		ans = ans * t % mod;
	}
	cout << ans << endl;
	return 0;
}

四，最大公约数

活动 - AcWing

思想：用辗转相除法效率最高

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int a, b;
        cin >> a >> b;
        //辗转相除，直到小括号内右边数为0
        while(b)
        {
            //c 一定小于 b
            int c = a % b;
            //小括号左边放除数，右边放约数
            a = b;
            b = c;
        }
        //小括号内左边数为最大公约数
        cout << a << endl;
    }
}

递归简化版文章来源地址https://www.toymoban.com/news/detail-665451.html

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
const long long mod = 1e9 + 7;

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

int main()
{
	int T;
	cin >> T;
	while (T--) {
		long long a, b;
		cin >> a >> b;
		cout << gcd(a, b) << endl;
	}
	return 0;
}

到了这里，关于数论----约数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！