Codeforces Round #767 (Div. 2) B. GCD Arrays

Solution

k operation 후에 gcd가 1이 아니면 충족하니 gcd를 2로 유도하는게 가장 최소의 operation을 하는 방법이다. 짝수는 gcd 2조건에 충족하니 홀수에 대해서 gcd 2를 유도해야한다.

먼저 [l, r] 의 범위에 홀수의 개수를 구하고 (((r - l) >> 1) + ((r & 1) | (l & 1))) 모든 홀수를 곱한 뒤 짝수 하나와 곱해준 수가 k보다 작거나 같으면 된다. 예외로 l == r인 케이스와 l == r != 1인 케이스를 처리하면 된다.

#include <iostream>

using namespace std;

int main() {
    int i, l, r, k;
    cin>>i;
    while(i--) {
        cin>>l>>r>>k;
        if((l == r and l != 1) or (((r - l) >> 1) + ((r & 1) | (l & 1))) <= k) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}