結果

問題 No.896 友達以上恋人未満
コンテスト
ユーザー 37zigen
提出日時 2018-02-24 01:00:12
言語 Java
(openjdk 23)
結果
RE  
実行時間 -
コード長 2,548 bytes
コンパイル時間 4,392 ms
コンパイル使用メモリ 79,036 KB
実行使用メモリ 309,684 KB
最終ジャッジ日時 2024-06-11 19:11:39
合計ジャッジ時間 4,592 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 6 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		long mulX = Long.parseLong(sc.next());
		long addX = Long.parseLong(sc.next());
		long mulY = Long.parseLong(sc.next());
		long addY = Long.parseLong(sc.next());
		long MOD = Long.parseLong(sc.next());
		long MOD2 = Long.parseLong(sc.next());
		long[] X = new long[M];
		long[] Y = new long[M];
		long[] A = new long[M];
		long[] B = new long[M];
		long[] w = new long[(int) MOD];
		long[] z = new long[(int) MOD];
		for (int i = 0; i < M; ++i)
			X[i] = Long.parseLong(sc.next());
		for (int i = 0; i < M; ++i)
			Y[i] = Long.parseLong(sc.next());
		for (int i = 0; i < M; ++i)
			A[i] = Long.parseLong(sc.next());
		for (int i = 0; i < M; ++i)
			B[i] = Long.parseLong(sc.next());
		for (int i = 0; i < M; ++i) {
			add(z, X[i], Y[i]);
			add(w, A[i], 1);
			add(w, A[i] * B[i], -1);
		}
		{
			long X_ = X[M - 1] & (MOD - 1);
			long Y_ = Y[M - 1] & (MOD - 1);
			long A_ = A[M - 1] & (MOD2 - 1);
			long B_ = B[M - 1] & (MOD2 - 1);
			for (int i = M; i < N; ++i) {
				X_ = X_ * mulX + addX & MOD - 1;
				Y_ = Y_ * mulY + addY & MOD - 1;
				A_ = ((A_ * mulX & MOD2 - 1) + addX + MOD2 - 1 & MOD2 - 1) + 1;
				B_ = ((B_ * mulY & MOD2 - 1) + addY + MOD2 - 1 & MOD2 - 1) + 1;
				add(z, X_, Y_);
				add(w, A_, 1);
				add(w, A_ * B_, -1);
			}
		}
		long all = 0;
		for (int i = 1; i < z.length; ++i) {
			if (w[i] != 0) {
				for (int j = i; j < z.length; j += i) {
					all += z[j] * w[i] & ((1 << 30) - 1);
					all &= (1 << 30) - 1;
				}
			}
		}
		rec = new long[(int) MOD + 1];
		Arrays.fill(rec, -1);
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < M; ++i) {
			long v = f(A[i], z) - f(A[i] * B[i], z) + (1 << 30);
			v &= (1 << 30) - 1;
			pw.println(v);
		}
		pw.println(all);
		pw.close();
	}

	long f(long v, long[] z) {
		if (v >= z.length)
			return 0;
		if (rec[(int) v] != -1)
			return rec[(int) v];
		rec[(int) v] = 0;
		for (int j = (int) v; j < z.length; j += v) {
			rec[(int) v] += z[j];
			rec[(int) v] &= (1 << 30) - 1;
		}
		return rec[(int) v];
	}

	long[] rec;

	void add(long[] arr, long idx, long v) {
		if (idx >= arr.length)
			return;
		v += 1 << 30;
		v &= (1 << 30) - 1;
		arr[(int) idx] += v;
		arr[(int) idx] &= (1 << 30) - 1;
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}
0