#1130994 (Java) No.3331 Consecutive Cubic Sum

• 問題: No.3331 Consecutive Cubic Sum
• ユーザー: 37zigen
• 提出日時: 2025-11-02 23:13:40
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 207 ms / 5,000 ms
• コード長: 7,523 bytes
• コンパイル時間: 2,621 ms
• コンパイル使用メモリ: 88,156 KB
• 実行使用メモリ: 49,980 KB
• 最終ジャッジ日時: 2025-11-02 23:13:55
• 合計ジャッジ時間: 10,594 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 3
other	AC * 47

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.TreeMap;
import java.util.function.DoubleUnaryOperator;
import java.util.function.LongToDoubleFunction;
import java.util.function.Predicate;

class FastScanner {
    private static FastScanner instance = null;

    private final InputStream in = System.in;

    private final byte[] buffer = new byte[1024];

    private int ptr = 0;

    private int buflen = 0;

    private FastScanner() {
    }

    public static FastScanner getInstance() {
        if (instance == null) {
            instance = new FastScanner();
        }
        return instance;
    }

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }
        ptr = 0;
        try {
            buflen = in.read(buffer);
        } catch (IOException e) {
            e.printStackTrace();
        }
        return buflen > 0;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private boolean isPrintableChar(int c) {
        return (33 <= c) && (c <= 126);
    }

    public boolean hasNext() {
        while (hasNextByte() && (!isPrintableChar(buffer[ptr]))) {
            ptr++;
        } 
        return hasNextByte();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        while ((b >= '0') && (b <= '9')) {
            n = (n * 10) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }
}

class MyPrintWriter extends PrintWriter {
    private static MyPrintWriter instance = null;

    private MyPrintWriter() {
        super(System.out);
    }

    public static MyPrintWriter getInstance() {
        if (instance == null) {
            instance = new MyPrintWriter();
        }
        return instance;
    }

    public void println(char[][] a) {
        for (int i = 0; i < a.length; i++) {
            println(a[i]);
        }
    }

    public void println(long[] a) {
        println(a, " ");
    }

    public void println(long[] a, String separator) {
        for (int i = 0; i < a.length; ++i) {
            super.print(a[i] + (i == (a.length - 1) ? "\n" : separator));
        }
    }
}

class MathUtils {
    /**
     * ニュートン法を用いて、sqrtを計算する。
     * x-f(x)/f'(x)=x-(x**2-n)/2x=x-x/2+n/(2x)=(x*x+n)/(2x)
     */
    public static int sqrt(long a) {
        if (a == 0) {
            return 0;
        }
        long ret = a;
        while (true) {
            long nret = (ret + (a / ret)) / 2;
            if (nret >= ret) {
                break;
            }
            ret = nret;
        } 
        return ((int) (ret));
    }

    /**
     * isLeft.test(i) = True となる最大の i を返す。
     * isLeft.test(left) = True, isLeft.test(right) = False　と仮定して動作する。
     *
     * @param left
     * @param right
     * @param isLeft
     * @return  */
    public static long binarySearch(long left, long right, Predicate<Long> isLeft) {
        while ((right - left) != 1) {
            long middle = left + ((right - left) / 2);
            if (isLeft.test(middle)) {
                left = middle;
            } else {
                right = middle;
            }
        } 
        return left;
    }

    public static long saturating_mul(long a, long b) {
        if ((a == 0) || (b == 0)) {
            return 0;
        }
        if ((a < 0) && (b < 0)) {
            if ((a == Long.MIN_VALUE) || (b == Long.MIN_VALUE)) {
                return Long.MIN_VALUE;
            }
            return MathUtils.saturating_mul(-a, -b);
        }
        if ((a > 0) && (b > 0)) {
            if (a <= (Long.MAX_VALUE / b)) {
                return a * b;
            }
            return Long.MAX_VALUE;
        }
        if ((a < 0) && (b > 0)) {
            if ((a == Long.MIN_VALUE) || (b == Long.MAX_VALUE)) {
                return Long.MIN_VALUE;
            }
            if (a >= (Long.MIN_VALUE / b)) {
                return a * b;
            }
            return Long.MIN_VALUE;
        }
        if ((a > 0) && (b < 0)) {
            if ((a == Long.MAX_VALUE) || (b == Long.MIN_VALUE)) {
                return Long.MIN_VALUE;
            }
            if (b >= (Long.MIN_VALUE / a)) {
                return a * b;
            }
            return Long.MIN_VALUE;
        }
        throw new AssertionError();
    }

    public static long saturatingPow(long a, long n) {
        if (n == 0) {
            return 1;
        }
        long x = MathUtils.saturatingPow(a, n / 2);
        x = saturating_mul(x, x);
        if ((n % 2) == 1) {
            x = saturating_mul(a, x);
        }
        return x;
    }

    public static long integerRoot(long x, int k) {
        if (k < 0) {
            throw new AssertionError();
        }
        if (k == 0) {
            return 1;
        }
        if (k == 1) {
            return x;
        }
        if (k == 2) {
            return sqrt(x);
        }
        return binarySearch(0, Long.MAX_VALUE, v -> saturatingPow(v, k) <= x);
    }
}

public class Main implements Runnable {
    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        // new Main().gen();
        // new Thread(null, new Main(), "MainThreadWithLargeStack", (1024 * 1024) * 1024).start();// 1024MBスタックを確保して実行
        // new Main().test();
        // new Main().gen();
        new Main().run();
        // MergeFilesTest.test();
    }

    void solve() {
        FastScanner sc = FastScanner.getInstance();
        MyPrintWriter pw = MyPrintWriter.getInstance();
        // for (long t = 1; t < 1000; t++) {
        // final long N=t;
        long N = sc.nextLong();
        var ans = new ArrayList<long[]>();
        for (long div = 1; ((div * div) * div) <= (4 * N); ++div) {
            if (((4 * N) % div) != 0) {
                continue;
            }
            long d = div;
            long A = MathUtils.binarySearch(0, MathUtils.integerRoot(N, 3) + 1, a -> {
                long m = MathUtils.saturating_mul(((2 * a) + d) + 1, (((((2 * a) * a) + ((2 * a) * d)) + (2 * a)) + (d * d)) + d);
                return m <= ((4 * N) / d);
            });
            if (MathUtils.saturating_mul(((2 * A) + d) + 1, (((((2 * A) * A) + ((2 * A) * d)) + (2 * A)) + (d * d)) + d) == ((4 * N) / d)) {
                ans.add(new long[]{ A + 1, d + A });
            }
        }
        Collections.sort(ans, (x, y) -> Arrays.compare(x, y));
        pw.println(ans.size());
        for (int i = 0; i < ans.size(); i++) {
            pw.println(ans.get(i));
        }
        // }
    }

    public void run() {
        var sc = FastScanner.getInstance();
        var pw = MyPrintWriter.getInstance();
        solve();
        // long ans=new Solver().sole(N, x, y);
        pw.flush();
    }
}