#1138408 (Java) No.3396 ChRisTmas memory

• 問題: No.3396 ChRisTmas memory
• ユーザー: 37zigen
• 提出日時: 2025-12-03 22:06:59
• 言語: Java (openjdk 23)
• 結果: AC
• 実行時間: 2,024 ms / 4,000 ms
• コード長: 14,179 bytes
• コンパイル時間: 3,244 ms
• コンパイル使用メモリ: 106,416 KB
• 実行使用メモリ: 77,836 KB
• 最終ジャッジ日時: 2025-12-03 22:07:50
• 合計ジャッジ時間: 48,224 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 40

ソースコード

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.BiFunction;
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()));
    }
}

/**
 * *
 * 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 void addLast(int v) {
        if (len == a.length) {
            resize(2 * len);
        }
        a[tail] = v;
        tail = (tail + 1) & (a.length - 1);
        ++len;
    }

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

    public boolean isEmpty() {
        return len == 0;
    }

    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;
    }

    @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 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 gcd(long a, long b) {
        a = Math.abs(a);
        b = Math.abs(b);
        if (a == 0) {
            return b;
        }
        return MathUtils.gcd(b % a, a);
    }

    public static long modPow(long a, long n, long mod) {
        if (n < 0) {
            long inv = MathUtils.modInv(a, mod);
            return MathUtils.modPow(inv, -n, mod);
        }
        if (n == 0) {
            return 1;
        }
        return (MathUtils.modPow((a * a) % mod, n / 2, mod) * ((n % 2) == 1 ? a : 1)) % mod;
    }

    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];
    }

    /**
     * x=0のときはエラー
     *
     * @param x
     * @return  */
    public static int floorLog2(long x) {
        if (x == 0) {
            throw new AssertionError();
        }
        return 63 - Long.numberOfLeadingZeros(x);
    }

    public static boolean isPrime(int mod) {
        if (mod == 2) {
            return true;
        }
        if ((mod == 1) || ((mod % 2) == 0)) {
            return false;
        }
        int[] testNumbers = new int[]{ 2, 7, 61 };
        int pow2 = Integer.lowestOneBit(mod - 1);
        int log = MathUtils.floorLog2(pow2);
        for (int a : testNumbers) {
            a %= mod;
            if (a == 0) {
                continue;
            }
            long x = MathUtils.modPow(a, (mod - 1) / pow2, mod);
            if ((x == 1) || (x == (mod - 1))) {
                continue;
            }
            for (int i = 0; i < log; i++) {
                x = (x * x) % mod;
                if (x == (mod - 1)) {
                    break;
                }
                if (i == (log - 1)) {
                    return false;
                }
            }
        }
        return true;
    }

    static int findFactor(int n) {
        if (isPrime(n)) {
            return n;
        }
        if ((n % 2) == 0) {
            return 2;
        }
        Random rnd = new Random();
        while (true) {
            long c = rnd.nextLong(1, n);
            long x = rnd.nextLong(1, n);
            long y = x;
            long d = 1;
            while ((d == 1) && (d != n)) {
                x = ((x * x) + c) % n;
                y = ((y * y) + c) % n;
                y = ((y * y) + c) % n;
                d = MathUtils.gcd(n, Math.abs(x - y));
                if ((d != 1) && (d != n)) {
                    return ((int) (d));
                }
            } 
        } 
    }

    public static Map<Integer, Integer> factor2(int n) {
        Map<Integer, Integer> ret = new TreeMap<>();
        for (long i = 2; (((1L * i) * i) <= n) && (i <= 1000); ++i) {
            int e = 0;
            while ((n % i) == 0) {
                n /= i;
                ++e;
            } 
            if (e != 0) {
                ret.put(((int) (i)), e);
            }
        }
        IntDeque que = new IntDeque();
        if (n != 1) {
            que.addLast(n);
        }
        while (!que.isEmpty()) {
            int m = que.pollFirst();
            int a = findFactor(m);
            if (m == a) {
                ret.merge(a, 1, Integer::sum);
            } else {
                que.addLast(a);
                que.addLast(m / a);
            }
        } 
        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.factor2(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.factor2(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);
            }
        }
    }
}