ACM寒假第四讲

一、有理数取余

设计思路

题目要求给出一个有理数 c=a/b，求 c mod 19260817的值。这个值被定义为 bx≡a(mod19260817) 的解。通过阅读讲义可以得知，此题求和需要用到扩展欧几里得算法来进行求解，之后套用模板即可得到结果。

设计代码

#include <iostream>
using namespace std;

const int P = 19260817;
int a, b;
int extendedGCD(int m, int n, int &x, int &y) {//扩展欧几里得算法，套用模板
	if (!n) {
		x = 1, y = 0;
		return m;
	}

	int d = extendedGCD(n, m % n, y, x);
	y -= m / n * x;
	return d;
}

int main() {
    scanf("%d %d",&a &b);
	int x, y;
	int d = extendedGCD(b, P, x, y);
	if (a % d)
		puts("Angry!");
	else
		printf("%ld\n", ((long) x * a / d % P + P) % P);
}

二、Minimal Coprime

设计思路

题目给定了正整数区间互质以及最小互质的概念，要求求出一个区间[l,r]中的最小互质区间个数。首先我们结合数论的知识，容易得到，一个数x与其下一个数x+1一定是互质的，这样可以得出，除了[1,1]区间之外，之后的所有[x,x+1]区间都是互质的，这就是我们要找到的最小区间。之后再进行思考，[l,r]中有多少个这种区间？因为最小互质区间长度为2，可以得出个数即为l-r，之后再对[1,1]进行特殊情况判读即可。

设计代码

#include <iostream>
using namespace std;

void solve(int l, int r) {
	int ans = r - l;//非特殊情况
	if (l == 1 && r == 1) {//[1,1]特殊情况
		cout << 1 << endl;
		return;
	}

	cout << ans << endl;
}

int main() {
	int t;
	int l, r;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> l >> r;
		solve(l, r);
	}
	return 0;
}

三、素数密度

设计思路

题目需求很简单，给定区间[L,R],求出区间中的个数。同样阅读讲义可以知道，求素数可以用到线性筛，用埃拉托斯特尼筛法即可得到所求个数。基本思路如下：首先使用一个bool数组标记每个数字是否为合数，之后再利用一个数组保存筛选出来的素数。对于[L,R]中的每一个整数i，如果i没有被标记。则i为素数，加入素数数组中；之后再遍历素数列表：对于每一个素数p，如果ixp<=R，那么ixp标记为合数；如果i能够被p整除，就停止便利即可。

设计代码

#include <iostream>
#include <vector>
using namespace std;

class LinearSieve {
	public:
		vector<long long int> primes;
		vector<bool> isComposite;
		LinearSieve(long long int n, long long int m) {
			isComposite.assign(m + 1, false);
			for (long long int i = n; i <= m; i++) {
				if (!isComposite[i]) {
					primes.push_back(i);
				}
				for (long long int p : primes) {
					if (i * p > m)
						break;
					isComposite[i * p] = true;
					if (i % p == 0)
						break;
				}
			}
		}
};

long long  read() {//快速读入
	long long s = 0, f = 1;
	char ch = getchar();

	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		s = s * 10 + ch - '0';
		ch = getchar();
	}
	return s * f;
}

int main() {
	long long int l, r;
	l = read();
	r = read();
	if (l < 2)
		l = 2;
	LinearSieve p(l, r);
	printf("%lld\n", p.primes.size());
	return 0;
}

四、最大公约数和最小公倍数问题

设计思路

这个题目要求输入两个正整数x0，y0，求满足P,Q是正整数并且以x0为最大公约数，以y0为最小公倍数的数对个数。首先进行观察，发现PxQ总是等于x0xy0，于是想到通过两层循环便利来求解数对个数。之后发现容易超时，对代码进行修改，采用单个循环即可解决。

设计代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	int x0, y0;
	scanf("%d%d", &x0, &y0);
	int maxn, minn;
	maxn = max(x0, y0);
	minn = min(x0, y0);
	int  count = 0;
	for (int P = minn; P <= maxn; P++) {
		if (x0 * y0 % P == 0) {
			if (__gcd(P, x0 * y0 / i) == x0) {//循环查找关键，因为x0*y0%i肯定是数对中的另一个数Q，而P，Q的最大公约数肯定要为x0才能进行下一步计算。
				count++;
			}
		}
	}
	printf("%d", count);
	return 0;
}

五、学习总结

在这次学习中，初步认识了数论在程序编程中的意义，其实在之前也学过一点点数论基础，不过没有运用到编程中来。这次也算进行了一个小小的结合，虽然在很多地方还是不甚了解，但是起码开了一个好头，之后还会继续学习下去。