結果

問題 No.896 友達以上恋人未満
ユーザー 37zigen
提出日時 2018-02-24 08:13:43
言語 Java
(openjdk 23)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,085 bytes
コンパイル時間 2,727 ms
コンパイル使用メモリ 78,436 KB
実行使用メモリ 302,864 KB
最終ジャッジ日時 2024-06-11 19:12:55
合計ジャッジ時間 3,216 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 4
other RE * 6 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        new Main().run();
    }
    long MASK = (1 << 30) - 1;
    void run() {
        FastScanner sc = new FastScanner();
        int M = (int) sc.nextLong();
        int N = (int) sc.nextLong();
        long mulX = sc.nextLong();
        long addX = sc.nextLong();
        long mulY = sc.nextLong();
        long addY = sc.nextLong();
        long MOD = sc.nextLong();
        long MOD2 = sc.nextLong();
        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] = sc.nextLong();
        for (int i = 0; i < M; ++i)
            Y[i] = sc.nextLong();
        for (int i = 0; i < M; ++i)
            A[i] = sc.nextLong();
        for (int i = 0; i < M; ++i)
            B[i] = sc.nextLong();
        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 << 30) - 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 << 30) - 1);
            }
        }
        for (int i = 0; i < w.length; ++i)
            w[i] &= MASK;
        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] & MASK) * w[i]) & MASK;
                    all &= MASK;
                }
            }
        }
        rec = new long[(int) MOD];
        Arrays.fill(rec, -1);
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < M; ++i) {
            pw.println(f(A[i], z) - f(A[i] * B[i], z));
        }
        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];
        }
        return rec[(int) v];
    }
    long[] rec;
    void add(long[] arr, long idx, long v) {
        if (idx >= arr.length)
            return;
        arr[(int) idx] += v;
    }
    class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() {
            if (hasNextByte())
                return buffer[ptr++];
            else
                return -1;
        }
        private boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }
        private void skipUnprintable() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr]))
                ptr++;
        }
        public boolean hasNext() {
            skipUnprintable();
            return hasNextByte();
        }
        public String next() {
            if (!hasNext())
                throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            if (!hasNext())
                throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
    }
    void tr(Object... objects) {
        System.out.println(Arrays.deepToString(objects));
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0