Codeforces Round 671 Div 1 C (абсолютная странность массива)
Codeforces 671 Div 1 C (абсолютная странность массива)
Пусть vi будет b1, b2, b3...bk. Обратите внимание, что наша l - r должна покрывать как минимум k - 1 из этих индексов. l должен быть меньше или равен b2.
Я смог понять первую часть решения, но кто-то может объяснить, пожалуйста, приведенное выше утверждение.
2 ответа
Потому что, если (l-r) охватывает менее k-1 индексы, то там должно быть x, y такой, что bx а также by вне диапазона [l, r], и потому что i | a[bx], i | a[by], затем gcd(a[bx], a[by]) >= i, что не правильно, потому что вы обновляете next от i в i-1,
Так как (l-r) охватывает по крайней мере k-1 элементы b1, ..., bk, так l должно быть меньше или равно b2,
Определить значение F(l,r), обозначить подпоследовательность A[1：n].
A [1.... (l-1), (r + 1)....] для расчета максимального значения gcd (A [i], A [j])
Sum = ∑ ∑F (i, j) (i! = J)