[백준 20359] A simple task (C#, C++) - soo:bak

문제 링크

20359번 - A simple task

설명

양의 정수를 홀수와 2의 거듭제곱의 곱으로 분해하는 문제입니다. n = o × 2^p 형태로 나타낼 때 o와 p를 구합니다.

접근법

n이 짝수인 동안 계속 2로 나누면서 나눈 횟수를 셉니다. 더 이상 2로 나누어지지 않을 때 남은 값이 홀수 o이고, 나눈 횟수가 p입니다.

비트 연산으로 최하위 비트가 0인지 확인하면 짝수 판별이 빠릅니다.

---

Code

C#

using System;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var p = 0;
    while ((n & 1) == 0) { n >>= 1; p++; }
    var o = n;
    Console.WriteLine($"{o} {p}");
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;

  int p = 0;
  while ((n & 1) == 0) { n >>= 1; p++; }
  int o = n;

  cout << o << " " << p << "\n";

  return 0;
}