結果
| 問題 | No.3396 ChRisTmas memory |
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2025-12-03 22:01:41 |
| 言語 | Java (openjdk 23) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 12,398 bytes |
| コンパイル時間 | 4,111 ms |
| コンパイル使用メモリ | 103,864 KB |
| 実行使用メモリ | 81,472 KB |
| 最終ジャッジ日時 | 2025-12-03 22:02:33 |
| 合計ジャッジ時間 | 50,967 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 38 MLE * 2 |
ソースコード
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.ArrayDeque;
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.Queue;
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()));
}
}
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);
}
}
Queue<Integer> que = new ArrayDeque<>();
if (n != 1) {
que.add(n);
}
while (!que.isEmpty()) {
int m = que.poll();
int a = findFactor(m);
if (m == a) {
ret.merge(a, 1, Integer::sum);
} else {
que.add(a);
que.add(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);
}
}
}
}