結果

問題 No.2963 Mecha DESU
ユーザー ks2m
提出日時 2024-11-16 16:15:48
言語 Java
(openjdk 23)
結果
AC  
実行時間 795 ms / 2,000 ms
コード長 1,503 bytes
コンパイル時間 2,955 ms
コンパイル使用メモリ 77,852 KB
実行使用メモリ 63,772 KB
最終ジャッジ日時 2024-11-16 16:16:22
合計ジャッジ時間 28,384 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int m = Integer.parseInt(sa[1]);
		int k = Integer.parseInt(sa[2]);
		sa = br.readLine().split(" ");
		int[] c = new int[1000001];
		for (int i = 0; i < m; i++) {
			int a = Integer.parseInt(sa[i]);
			c[a]++;
		}
		br.close();

		int[] b = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			int ci = c[i];
			if (ci > 0) {
				for (int j = i; j <= n; j += i) {
					b[j] += ci;
				}
			}
		}

		int mod = 998244353;
		long mk = power(m, k, mod);
		long total = n * mk % mod;
		long rem = 0;
		for (int i = 1; i <= n; i++) {
			long val = power(m - b[i], k, mod);
			rem += val;
		}
		rem %= mod;
		long ans = (total - rem + mod) % mod;
		ans *= modinv(mk, mod);
		ans %= mod;
		System.out.println(ans);
	}

	static long power(long x, long n, int m) {
		if (n == 0) {
			return 1;
		}
		long val = power(x, n / 2, m);
		val = val * val % m;
		if (n % 2 == 1) {
			x %= m;
			val = val * x % m;
		}
		return val;
	}

	static long modinv(long a, int m) {
		long b = m;
		long u = 1;
		long v = 0;
		long tmp = 0;

		while (b > 0) {
			long t = a / b;
			a -= t * b;
			tmp = a;
			a = b;
			b = tmp;

			u -= t * v;
			tmp = u;
			u = v;
			v = tmp;
		}

		u %= m;
		if (u < 0) u += m;
		return u;
	}
}
0