#1138385 (Java) No.3396 ChRisTmas memory

• 問題: No.3396 ChRisTmas memory
• ユーザー: 37zigen
• 提出日時: 2025-12-03 20:44:04
• 言語: Java (openjdk 23)
• 結果: TLE
• 実行時間: -
• コード長: 9,551 bytes
• コンパイル時間: 4,251 ms
• コンパイル使用メモリ: 102,432 KB
• 実行使用メモリ: 58,664 KB
• 最終ジャッジ日時: 2025-12-03 20:44:16
• 合計ジャッジ時間: 11,346 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
sample	AC * 2
other	AC * 5 TLE * 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.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;
}

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();
        int[] m = new int[10000];
        int[] r = new int[10000];
        int msize = 0;
        int rsize = 0;
        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 < msize; i++) {
                    res = (res + (fac * r[i])) % M;
                    fac = (fac * m[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[msize++] = coprimeM;
                r[rsize++] = ((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[msize - 1]);
                    for (var es : factor.entrySet()) {
                        var erque = ermap.get(es.getKey().intValue());
                        erque.pop();
                        if (erque.isEmpty()) {
                            ermap.remove(es.getKey().intValue());
                        }
                    }
                    msize--;
                    rsize--;
                }
            } else {
                long mod = sc.nextInt();
                long ans = 0;
                long fac = 1;
                for (int i = 0; i < msize; i++) {
                    ans += fac * r[i];
                    ans %= mod;
                    fac = (fac * m[i]) % mod;
                }
                ans = ((ans % mod) + mod) % mod;
                pw.println(ng == 0 ? ans : -1);
            }
        }
    }
}