본문 바로가기

CP_contest_Review

Codeforces R697 D3

반응형

solved 1 out of 7

 

서버 문제로인해 대회가 미뤄지기도하고 채점이 진행되지않아 B번까지 보다가 그냥 잤습니다.

너무 아쉽지만 A번을 특이하게 풀어서 기록을 남깁니다.

 

A. Odd Divisor

주어진 정수 N이 홀수로 나눠지는지 확인하는 문제입니다.

다만 이때 N의 크기가 1014임으로 O(N)으로 찾아주면 안됩니다.

 

N이 홀수면, N은 무조건 Odd Divisor를 갖는다는 점을 활용하여 문제를 해결할 수 있습니다.

 

func(N) {
	if N=odd return true
	else if N=even func(n/2)
}

이렇게 N을 절반씩 나눠주면 O(logN)안에 문제를 풀 수 있습니다.

 

bool chk(ll k) {
    if (k%2!=0) return true;
    return false;
}
bool sol(ll n) {
    bool ans = false;
    if (n==1) return ans;
    if (chk(n)) return true;
    else {
        ll tmp = n/2;
        if (sol(tmp)) ans=true;
        else ans=false;
    }
    return ans;
}
int main(void) {
    fast_cin();
    int tc;read(tc);
 
    while (tc--) {
        ll n;read(n);
        if(sol(n)) cout << "yes" << endl;
        else cout << "no" << endl;
    }
 
    return 0;
}

 

 

 

반응형

'CP_contest_Review' 카테고리의 다른 글

AtCoder ABC 190  (0) 2021.01.31
codeforces R698 D2  (0) 2021.01.29
CF R696 D2  (0) 2021.01.20
ABC 188  (0) 2021.01.11
Goodbye 2020  (0) 2021.01.02