基本情况

最难受的一集。

A搞了一个半小时愣是没开出来。

A. Difference Operations

Problem - A - Codeforces

错误分析

我分了好多类讨论，换言之没找到更本质的东西。

我想的是如果前面有一个数能处理到 \(1\) 那后面就都能过。

止步于此，而没有往更本质，更普适的地方想。

然后又讨论了很多特例，但是果然还是死在了 test8。

以后当思路陷入这种分了一堆类讨论的时候一定要考虑换思路，很可能这个思路就是错的。

附上逆天代码：

int a[102], n;

void solve()
{
	std::cin >> n >> a[1];
	int cnt = 0;
	for (int i = 2; i <= n; i++) 
	{
		std::cin >> a[i];
		if (a[i] % a[i - 1] == 0) cnt++;
	}
	if (cnt == n - 1) {std::cout << "YES\n"; return ;}
	if (a[2] % a[1] != 0) {std::cout << "NO\n"; return ;}
	for (int i = 2; i<= n; i++)
	{
		if (a[i] < a[i - 1]) {std::cout << "NO\n"; return ;}
		if (a[i] % a[i - 1] == 0)
		{
			a[i] = a[i - 1];
		}
		else
		{
			a[i] = a[i] % a[i - 1];
		}
	}
	if (a[n] % a[n - 1] == 0)
		std::cout << "YES\n";
	else
		std::cout << "NO\n";
}

正确思路

我们分数列中的各个数分析。

对于 \(a_2\)，要使其为 \(0\)，由于 \(a_2\) 只能靠 \(a_1\) 来修改，故当且仅当 \(a_1|a_2\) 时才可操作。

下面这一步我没推出来，或者说推出来的东西仅仅是\(1\)，没有往更本质的地方向

对于 \(a_3\)，只能靠 \(a_2\) 来修改，若仅考虑原始的 \(a_2\)，则 \(a_2|a_3\)，但是由于 \(a_2\) 可以被 \(a_1\) 修改且满足 \(a_1|a_2\)，于是只需使 \(a_1|a_3\) 即可使 \(a_3=0\)。

其余同理，故对于原始序列，当且仅当 \(\forall a_1|a_i,i\in\left[2,n\right]\) 返回 YES；其他情况均返回 NO。

样例均可作为例子进行验证，模拟较为简单，此处不再赘述。

单组数据时间复杂度 \(\mathcal{O}(n)\)，可以在线处理也可离线处理。

以离线处理为例。

int a[105], n;

void solve()
{
	std::cin >> n;
	for (int i = 1; i <= n; i++) 
	{
		std::cin >> a[i];
	}
	for (int i = 2; i <= n; i++)
	{
		if (a[i] % a[1]) {std::cout << "NO\n"; return ;}
	}
	std::cout << "YES\n"; return ;
}

B. Difference of GCDs

Problem - B - Codeforces

题意

给出 \(n,l,r\)，构造 \(a\)，使得对于任意 \(\gcd(a_i,i)\) 不相同。

明确一点：\(a_i\) 不一定不相同，这也是我方法正确的关键之处。

思路

约定：以下叙述中，\(m\) 为正整数。

我们要想到结果必定是 \(\gcd(a_i,i)=i\)。

证明也很简单，因为 \(\gcd(a_i,i)\in[1,i]\)，而 \([1,i-1]\) 都被用过了，所以只能是 \(i\)。

问题转换为如何求 \(a_i\in[l,r]\) 为 \(i\) 的倍数。

首先，显然 \(a_i\) 必定为 \(im\)，此处先求最大的可能的 \(m=\lfloor\dfrac r i\rfloor\)。

那么 \(\max\left\{a_i\right\}=mi=\lfloor\dfrac r i\rfloor\times i\)。

无解更简单，\(a_i\) 已经最大了，如果依然小于 \(l\)，那 \([l,r]\) 中就必定没有合理的 \(a_i\) 了。

注意，如果 \(a_i\) 互不相同，这个做法就不正确了。

代码

const int N = 2e5;
int ans[N];

void solve()
{
	int n, l, r;
	std::cin >> n >> l >> r;
	for (int i = 1; i <= n; i++)
	{
		if (r / i * i < l)
		{
			std::cout << "NO\n";
			return ;
		}
		ans[i] = r / i * i;//ai是可以相同的 
	}
	std::cout << "YES\n";
	for (int i = 1; i <= n; i++) std::cout << ans[i] << " ";
	std::cout << std::endl;
}