博客

《算法基础》 约数

1.试除法求约数

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

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

int main()
{
	int n;
	cin >> n;
	while (n --) {
		int c;
		cin >> c;
		auto res = get_divides(c);
		for (auto t : res) {
			cout << t << " ";
		}
		cout << endl;
	}
	return 0;
}

2.求约数个数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <unordered_map>
using namespace std;

typedef long long LL;
const int N = 110, 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) {
				x /= i;
				primes[i] ++;
			}
		}
		if (x > 1)
			primes[x] ++;
	}
	LL res = 1;
	for (auto prime : primes) {
		res = res * (prime.second + 1) % mod;
	}
	cout << res << endl;

	return 0;
}

3.约数之和

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long LL;

const int N = 110, 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) {
				x /= i;
				primes[i] ++;
			}
		}
		if (x > 1) primes[x] ++;
	}
	
	LL res = 1;
	for (auto prime : primes) {
		LL p = prime.first, a = prime.second;
		LL t = 1;
		while (a --) {
			t = (t * p + 1) % mod;
		}
		res = res * t % mod;
	}
	cout << res << endl;
	return 0;
}

4.欧几里得算法

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

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

int main()
{
	int n;
	cin >> n;
	while (n --) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d", gcd(x, y));
	}
	return 0;
}