거듭제곱쌓아 가기P0050

넘지 않는 거듭제곱

정수 a와 N이 빈칸으로 나뉘어 한 줄에 주어진다.
a의 거듭제곱 a^0, a^1, a^2, … 가운데 N 이하인 것을 작은 것부터 한 줄에 하나씩 모두 출력하라.
a^0 = 1이고 N ≥ 1이므로 첫 줄은 언제나 1이다.

입력: 2 ≤ a ≤ 1,000,000,000, 1 ≤ N ≤ 9,000,000,000,000,000 (9 × 10^15)
출력: N 이하인 a^k를 k = 0부터 차례로, 한 줄에 하나씩

예시 1 · stdin

2 100

stdout

예시 2 · stdin

10 1000

stdout

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

거듭제곱을 매번 새로 구하지 말고 앞의 값에 a를 곱해 쌓아 가면 돼요(p = 1에서 시작해 p *= a).
함정 셋.
① ^는 거듭제곱이 아니에요: C·C++·Java·C#·JS·TS에서 2 ^ 3은 비트 XOR이라 1이에요.
거듭제곱 연산자는 Python·JS·TS의 **뿐이고, C·C++은 pow, Java Math.pow, C# Math.Pow(모두 double), 크레이콘에는 거듭제곱이 없어 곱하기 반복으로 만들어요.
② 넘침: 마지막 p가 9×10^15 가까이에서 a(최대 10억)를 한 번 더 곱하면 long 범위(약 9.2×10^18)를 넘어요.
C·C++·Java·C#은 넘쳐도 오류 없이 값이 돌아서(C·C++은 정의되지 않은 동작) 65537^4 같은 값이 9×10^15보다 작은 수가 되어 엉뚱한 줄이 더 찍혀요.
곱하기 전에 p > N / a로 멈출지 물어보세요.
Python 정수는 커져도 넘치지 않고, JS·TS·크레이콘은 실수라 넘치는 대신 부정확해지지만 그때는 이미 N보다 커서 p <= N만으로 맞아요.
③ int: 2^31을 넘으니 C·C++·Java·C#은 long(long long)이어야 해요.

Pythonmain.py · 5 줄

a, n = map(int, input().split())p = 1  # a의 0제곱while p <= n:    print(p)    p *= a  # 파이썬 정수는 커져도 넘치지 않는다

JavaScriptmain.js · 5 줄

const [a, n] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out = [];// p * a가 2^53을 넘으면 정확하지 않지만, 그때는 이미 n보다 커서 반복이 끝난다for (let p = 1; p <= n; p *= a) out.push(p);console.log(out.join("\n"));

TypeScriptmain.ts · 6 줄

import { readFileSync } from "node:fs";const [a, n]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out: number[] = [];// p * a가 2^53을 넘으면 정확하지 않지만, 그때는 이미 n보다 커서 반복이 끝난다for (let p = 1; p <= n; p *= a) out.push(p);console.log(out.join("\n"));

JavaMain.java · 17 줄

import java.util.Scanner; public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        long a = sc.nextLong(), n = sc.nextLong();        StringBuilder out = new StringBuilder();        long p = 1;        while (true) {            out.append(p).append('\n');            // p * a는 long도 넘칠 수 있다 → 곱하기 전에 나눗셈으로 확인            if (p > n / a) break;            p *= a;        }        System.out.print(out);    }}

C#Main.cs · 18 줄

using System; class Program{    static void Main()    {        string[] t = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        long a = long.Parse(t[0]), n = long.Parse(t[1]);        long p = 1;        while (true)        {            Console.WriteLine(p);            // p * a는 long도 넘칠 수 있다(C#은 기본이 unchecked라 조용히 돈다) → 곱하기 전에 확인            if (p > n / a) break;            p *= a;        }    }}

C++main.cpp · 13 줄

#include <iostream> int main() {    long long a, n;    std::cin >> a >> n;    long long p = 1;    while (true) {        std::cout << p << '\n';        // p * a는 long long도 넘칠 수 있다 → 곱하기 전에 나눗셈으로 확인        if (p > n / a) break;        p *= a;    }}

Cmain.c · 14 줄

#include <stdio.h> int main(void) {    long long a, n;    scanf("%lld %lld", &a, &n);    long long p = 1;    for (;;) {        printf("%lld\n", p);        /* p * a는 long long도 넘칠 수 있다 → 곱하기 전에 나눗셈으로 확인 */        if (p > n / a) break;        p *= a;    }    return 0;}

Craykonmain.cray · 10 줄

수들 = 콘솔.수들읽기();a = 수들[0];n = 수들[1];// 크레이콘 수는 실수라 넘치지 않는다. 2^53을 넘으면 정확하지 않지만 그때는 이미 n보다 크다p = 1;동안 (p <= n){    콘솔.쓰기(p);    p *= a;}