Codeforces R697 D3

solved 1 out of 7

 

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

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

 

A. Odd Divisor

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

다만 이때 N의 크기가 $10^{14}$임으로 $O\left ( N \right )$으로 찾아주면 안됩니다.

 

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

 

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

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

 

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;
}