【数论】约数

试除法求约数

时间复杂度 O(sqrt(n))。

核心思路是求到较小的约数时，将其对应的较大约数也可以直接求出来，

例如：a/b=c，b是a的余数，c也是a的余数

ps：注意b==c的情况，要注意去重

void solve() {
	int n; cin >> n;
	vector<int> ans;
	for (int i = 1; i <= n / i; i++) {
		if (n % i == 0) {
			ans.push_back(i);
			if (i != n / i) ans.push_back(n / i);//去重
		}
	}
	sort(ans.begin(), ans.end());
	for (auto x : ans) {
		cout << x << " ";
	}
	cout << endl;
}

前置知识，分解质因数

n =?

p是质因数

void solve() {
	int n; cin >> n;
	map<int, int> mp;
	int c; cin >> c;
	for (int i = 2; i <= c / i; i++) {
		while (c % i == 0) {
			c /= i;
			mp[i]++;
		}

	}

	if (c > 1) mp[c]++;
    //如果c本身就是质数，例如7，
    //那么它就大于sqrt(c)，因此要特判

}

约数个数

假设现在有一个n，它可以被分解为n =?

假设d是n的一个约数，d可以被分解为 d =??

那么的不同，表示的约数也就不同。且 0<=<=。

因此会有个约数。

const int mod = 1e9 + 7;
void solve() {
	int n; cin >> n;
	map<int, int> mp;
	while (n--) {
		int c; cin >> c;
		for (int i = 2; i <= c / i; i++) {
			while (c % i == 0) {
				c /= i;
				mp[i]++;
			}

		}

		if (c > 1) mp[c]++;
	}

	int res = 1;
	for (auto it : mp) {
		res = res * (it.second + 1) % mod;
	}
	cout << res << endl;
}


signed main()
{
	int t; t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

约数之和

前置知识：秦九昭算法

?秦九昭算法，也称“快速幂求多项式值算法”，是一种高效地计算一个多项式在某个点的取值的方法。它利用了快速幂算法的思想，在O(logn)的时间复杂度内计算出多项式在某个点的值。

对于一个n次多项式f(x)，它可以表示为：

秦九昭算法利用了多项式的特殊性质，将上述公式转化为如下形式：

这个公式可以看作是从后往前逐项累加的过程，每次累加时都将上一项的结果乘以�x再加上当前项的系数。这个过程可以通过一个循环来实现，每次迭代都将当前项的系数与上一次迭代的结果相乘，再加上上一次迭代的结果，最终得到多项式在x0?处的值。

具体来说，可以用如下的代码实现：

double p = a[n];
for (int i = n - 1; i >= 0; --i) {
    p = a[i] + x * p;
}

公式：

?

原理：把这个式子展开，会发现枚举了每种约数（指数不同，约数就不同），并将他们加起来，便是约数之和了。

程序怎么写呢，这里要用到秦九昭算法，由于我们约数求和公式里的ai = 1，因此程序写成

int res = 1;
	for (auto it : mp) {
		int p = it.first, k = it.second;
		int temp = 1;
		while (k--) {
			temp = (temp * p + 1) % mod;
		}
		res = res * temp % mod;

	}
	cout << res << endl;

完整代码

int mod = 1e9 + 7;
void solve() {
	int n; cin >> n;
	map<int, int> mp;
	while (n--) {
		int c; cin >> c;
		for (int i = 2; i <= c / i; i++) {
			while (c % i == 0) {
				c /= i;
				mp[i]++;
			}

		}

		if (c > 1) mp[c]++;
	}

	int res = 1;
	for (auto it : mp) {
		int p = it.first, k = it.second;
		int temp = 1;
		while (k--) {
			temp = (temp * p + 1) % mod;
		}
		res = res * temp % mod;

	}
	cout << res << endl;
}


signed main()
{
	int t; t = 1;
	//cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

最大公约数，欧几里得算法

前置知识：

若 a%d==0，b%d==0，则 (ax+by) % d == 0

我们要求a，b的最大公约数。假设最大公约数是d

公式 gcd(a,b) == gcd(b,a%b)，这是核心，这个公式为什么成立呢？往下看

原理：因为 a%b = a-()*b，把设为c，那么就是 a%b = a-c*b，

惊奇地发现这个式子满足(ax+by) % d == 0。

因此对于 gcd(b,a%b)，d是b和a%b的约数，那么公式gcd(a,b) == gcd(b,a%b)就成立了。

当b <=?0时，此时的a就是最大公约数。

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