「Note」2021-08-19 做题记录

咕咕了一天，来写一个

A-F

例题果断咕咕。

G

link

分析

由裴蜀定理:$ax+by=d\times \gcd(a, b)$。可知$\min (ax+by) = \gcd(a,b)$

那么从两个数推广到$n$个数可知$\min(A_1X_1+A_2X_2+A_3X_3+...+A_nX_n)=\gcd(A_1, A_2, A_3, \dots ,A_n)$

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int n, ans;
int gcd (int x, int y) {
	if (y == 0) return x;
	else return gcd (y, x % y);
}
 
signed main () {
	scanf ("%lld", &n);
	for (int i = 1, x; i <= n; i++) {
		scanf ("%lld", &x);
		ans = gcd (ans, x);
	}
	printf ("%lld\n", ans < 0 ? -ans : ans);
	return 0;
}

Border

link

分析

即使要求$(A_1X_1+A_2X_2+A_3X_3+...+A_nX_n) \mod k$的所有值。

由上一题可知：$\min(A_1X_1+A_2X_2+A_3X_3+...+A_nX_n)=\gcd(A_1, A_2, A_3, \dots ,A_n)$

那么$(A_1X_1+A_2X_2+A_3X_3+...+A_nX_n) = d \times \gcd(A_1, A_2, A_3, \dots ,A_n)$

求出$\gcd$后枚举即可。

C Looooops

link

开始一直没看懂题

分析

即是求$a+cx $