#1138384 (Java) No.3396 ChRisTmas memory

• 問題: No.3396 ChRisTmas memory
• ユーザー: 37zigen
• 提出日時: 2025-12-03 20:34:25
• 言語: Java (openjdk 23)
• 結果: MLE
• 実行時間: -
• コード長: 11,458 bytes
• コンパイル時間: 3,582 ms
• コンパイル使用メモリ: 102,688 KB
• 実行使用メモリ: 81,356 KB
• 最終ジャッジ日時: 2025-12-03 20:34:38
• 合計ジャッジ時間: 11,390 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 5 MLE * 1 -- * 34

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.PrimitiveIterator.OfInt;
import java.util.PrimitiveIterator;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.Vector;
import java.util.function.DoubleUnaryOperator;
import java.util.function.IntFunction;
import java.util.function.IntToDoubleFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.LongToDoubleFunction;
import java.util.function.Predicate;
import java.util.function.ToIntFunction;
import java.util.random.RandomGenerator;
import java.util.stream.IntStream;
import java.util.stream.LongStream;
import java.util.stream.Stream;

class BitVector {
    final int lg = 5;
}

/**
 * *
 * lenがa.lengthに比べて小さくなっても配列を取り直さない。
 *
 * @param <T>
 */
class IntDeque implements Iterable<Integer> {
    @SuppressWarnings("unchecked")
    int[] a = new int[16];

    int head = 0;

    int tail = 0;

    int len = 0;

    // [head, tail)に値を持つ。
    public IntDeque() {
    }

    public int peekLast() {
        return a[(tail - 1) & (a.length - 1)];
    }

    public void addLast(int v) {
        if (len == a.length) {
            resize(2 * len);
        }
        a[tail] = v;
        tail = (tail + 1) & (a.length - 1);
        ++len;
    }

    public int pollLast() {
        if (len == 0) {
            throw new NoSuchElementException();
        }
        int ret = a[(tail - 1) & (a.length - 1)];
        tail = (tail - 1) & (a.length - 1);
        len--;
        return ret;
    }

    public int get(int id) {
        if ((id < 0) || (id >= len)) {
            throw new IndexOutOfBoundsException();
        }
        return a[(head + id) & (a.length - 1)];
    }

    void resize(int size) {
        @SuppressWarnings("unchecked")
        int[] na = new int[size];
        for (int i = 0; i < len; i++) {
            na[i] = a[(head + i) & (a.length - 1)];
        }
        head = 0;
        tail = len;
        a = na;
    }

    public int size() {
        return len;
    }

    @Override
    public PrimitiveIterator.OfInt iterator() {
        return new PrimitiveIterator.OfInt() {
            int idx = 0;

            @Override
            public boolean hasNext() {
                return idx < len;
            }

            @Override
            public int nextInt() {
                if (!hasNext()) {
                    throw new NoSuchElementException();
                }
                return get(idx++);
            }
        };
    }
}

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');
            n = ((n << 1) + (n << 3)) + (b - '0');
            b = readByte();
        } 
        return minus ? -n : n;
    }

    public int nextInt() {
        return ((int) (nextLong()));
    }
}

class PolynomialFp {
    public static final long mod = 998244353;
}

/**
 * Fp[X1,X2,..]/(1-X1^1, 1-X2^2, ..)
 */
class InvolutivePolynomialFp {
    static final long mod = 998244353;
}

class ArrayUtils {
    public static void swap(long[] A, long[] B) {
        if (A.length != B.length) {
            throw new AssertionError();
        }
        for (int i = 0; i < A.length; i++) {
            long tmp = A[i];
            A[i] = B[i];
            B[i] = tmp;
        }
    }
}

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(boolean[][] a) {
        for (int i = 0; i < a.length; i++) {
            println(a[i], " ");
        }
    }

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

class MathUtils {
    public static long pow(long a, long n) {
        if (n == 0) {
            return 1;
        }
        return MathUtils.pow(a * a, n / 2) * ((n % 2) == 1 ? a : 1);
    }

    /**
     * 拡張ユークリッドの互除法で逆元を求める。
     *
     * @param a
     * @param mod
     * @return  */
    public static long modInv(long a, long mod) {
        a = ((a % mod) + mod) % mod;
        long[] f0 = new long[]{ 1, 0, mod };
        long[] f1 = new long[]{ 0, 1, a };
        while (f1[2] != 0) {
            long q = f0[2] / f1[2];
            for (int i = 0; i < 3; i++) {
                f0[i] -= q * f1[i];
            }
            ArrayUtils.swap(f0, f1);
        } 
        return f0[1] < 0 ? mod + f0[1] : f0[1];
    }

    public static Map<Long, Integer> factor(long n) {
        Map<Long, Integer> ret = new TreeMap<>();
        for (long i = 2; ((1L * i) * i) <= n; ++i) {
            int e = 0;
            while ((n % i) == 0) {
                n /= i;
                ++e;
            } 
            if (e != 0) {
                ret.put(i, e);
            }
        }
        if (n != 1) {
            ret.put(n, 1);
        }
        return ret;
    }
}

public class Main implements Runnable {
    public static void main(String[] args) throws IOException {
        Thread.setDefaultUncaughtExceptionHandler((t, e) -> System.exit(1));
        // new Main().gen();
        // Runtime runtime = Runtime.getRuntime();
        // new Thread(null, new Main(), "MainThreadWithLargeStack", (1024 * 1024) * 1024).start();
        // new Main().test();
        // new Main().gen();
        new Main().run();
        // new Main().solve();
        // long usedMemory = runtime.totalMemory() - runtime.freeMemory();
        // System.err.printf("使用メモリ: %.2f MB%n", usedMemory / 1024.0 / 1024.0);
        MyPrintWriter.getInstance().flush();
    }

    @Override
    public void run() {
        FastScanner sc = FastScanner.getInstance();
        MyPrintWriter pw = MyPrintWriter.getInstance();
        int Q = sc.nextInt();
        IntDeque m = new IntDeque();
        IntDeque r = new IntDeque();
        Map<Integer, Stack<int[]>> ermap = new HashMap<>();
        int ng = 0;
        for (int q = 0; q < Q; q++) {
            int type = sc.nextInt();
            if (type == 1) {
                if (ng > 0) {
                    ng++;
                }
                int M = sc.nextInt();
                int R = sc.nextInt();
                int coprimeM = M;
                var factor = MathUtils.factor(M);
                long res = 0;
                long fac = 1;
                for (int i = 0; i < m.size(); i++) {
                    res = (res + (fac * r.get(i))) % M;
                    fac = (fac * m.get(i)) % M;
                }
                long g = 1;
                int coprimeFac = ((int) (fac));
                out : for (var es : factor.entrySet()) {
                    int p = es.getKey().intValue();
                    int e = es.getValue().intValue();
                    int pe = ((int) (MathUtils.pow(p, e)));
                    if (ermap.containsKey(es.getKey().intValue())) {
                        int[] er2 = ermap.get(es.getKey().intValue()).peek();
                        int e2 = er2[0];
                        int r2 = er2[1];
                        int pe2 = ((int) (MathUtils.pow(p, e2)));
                        if ((R % Math.min(pe, pe2)) != (r2 % Math.min(pe, pe2))) {
                            if (ng == 0) {
                                ng = 1;
                            }
                        }
                        if (er2[0] >= e) {
                            coprimeM /= pe;
                            continue out;
                        }
                        g *= pe2;
                    } else {
                        ermap.put(es.getKey().intValue(), new Stack<int[]>());
                    }
                    ermap.get(es.getKey().intValue()).add(new int[]{ e, R % pe });
                }
                coprimeFac %= coprimeM;
                long x = (((1L * (R - res)) / g) * MathUtils.modInv(coprimeFac / g, coprimeM / g)) % (coprimeM / g);
                coprimeM /= g;
                if (x < 0) {
                    x += coprimeM;
                }
                m.addLast(coprimeM);
                r.addLast(((int) (x)));
                // res+fac*x==R mod M
                // fac*x=R-res mod M
            } else if (type == 2) {
                int k = sc.nextInt();
                for (int i = 0; i < k; i++) {
                    ng = Math.max(ng - 1, 0);
                    var factor = MathUtils.factor(m.peekLast());
                    for (var es : factor.entrySet()) {
                        var erque = ermap.get(es.getKey().intValue());
                        erque.pop();
                        if (erque.isEmpty()) {
                            ermap.remove(es.getKey().intValue());
                        }
                    }
                    m.pollLast();
                    r.pollLast();
                }
            } else {
                long mod = sc.nextInt();
                long ans = 0;
                long fac = 1;
                for (int i = 0; i < m.size(); i++) {
                    ans += fac * r.get(i);
                    ans %= mod;
                    fac = (fac * m.get(i)) % mod;
                }
                ans = ((ans % mod) + mod) % mod;
                pw.println(ng == 0 ? ans : -1);
            }
        }
    }
}