#1027046 (Java21) No.2963 Mecha DESU

提出ソース

結果

問題	No.2963 Mecha DESU
ユーザー	ks2m
提出日時	2024-11-16 16:15:48
言語	Java21 (openjdk 21)
結果	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	54 ms 53,956 KB
testcase_01	AC	55 ms 54,140 KB
testcase_02	AC	56 ms 53,948 KB
testcase_03	AC	54 ms 54,464 KB
testcase_04	AC	55 ms 54,296 KB
testcase_05	AC	56 ms 54,348 KB
testcase_06	AC	56 ms 54,260 KB
testcase_07	AC	56 ms 54,508 KB
testcase_08	AC	55 ms 54,120 KB
testcase_09	AC	57 ms 54,364 KB
testcase_10	AC	54 ms 54,356 KB
testcase_11	AC	56 ms 54,076 KB
testcase_12	AC	55 ms 54,404 KB
testcase_13	AC	795 ms 63,772 KB
testcase_14	AC	751 ms 53,600 KB
testcase_15	AC	772 ms 53,744 KB
testcase_16	AC	722 ms 53,944 KB
testcase_17	AC	764 ms 53,900 KB
testcase_18	AC	727 ms 53,968 KB
testcase_19	AC	726 ms 54,060 KB
testcase_20	AC	494 ms 50,036 KB
testcase_21	AC	325 ms 53,056 KB
testcase_22	AC	173 ms 45,900 KB
testcase_23	AC	250 ms 52,956 KB
testcase_24	AC	527 ms 49,956 KB
testcase_25	AC	548 ms 52,704 KB
testcase_26	AC	619 ms 51,304 KB
testcase_27	AC	355 ms 47,128 KB
testcase_28	AC	682 ms 53,740 KB
testcase_29	AC	554 ms 53,160 KB
testcase_30	AC	126 ms 43,404 KB
testcase_31	AC	341 ms 49,696 KB
testcase_32	AC	215 ms 45,620 KB
testcase_33	AC	570 ms 52,804 KB
testcase_34	AC	497 ms 53,528 KB
testcase_35	AC	305 ms 48,088 KB
testcase_36	AC	464 ms 50,200 KB
testcase_37	AC	287 ms 52,924 KB
testcase_38	AC	274 ms 45,692 KB
testcase_39	AC	486 ms 51,332 KB
testcase_40	AC	410 ms 46,716 KB
testcase_41	AC	632 ms 50,856 KB
testcase_42	AC	540 ms 52,852 KB
testcase_43	AC	680 ms 53,376 KB
testcase_44	AC	623 ms 50,532 KB
testcase_45	AC	651 ms 50,208 KB
testcase_46	AC	373 ms 49,936 KB
testcase_47	AC	379 ms 46,388 KB
testcase_48	AC	324 ms 50,156 KB
testcase_49	AC	351 ms 44,764 KB
testcase_50	AC	773 ms 53,632 KB
testcase_51	AC	757 ms 53,444 KB
testcase_52	AC	681 ms 53,652 KB
testcase_53	AC	593 ms 51,128 KB
testcase_54	AC	662 ms 50,800 KB
testcase_55	AC	54 ms 40,572 KB
testcase_56	AC	54 ms 40,520 KB
testcase_57	AC	113 ms 45,968 KB
testcase_58	AC	234 ms 52,996 KB
testcase_59	AC	56 ms 40,832 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード