結果

問題 No.1529 Constant Lcm
コンテスト
ユーザー bal4u
提出日時 2021-08-15 07:51:14
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 338 ms / 3,000 ms
コード長 1,617 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 73,088 KB
最終ジャッジ日時 2024-10-06 20:12:52
合計ジャッジ時間 4,485 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yuki 1529 Constant Lcm
// 2021.8.15

#include <stdio.h>

typedef long long ll;
const int mod = 998244353;

#define MAX  1000005
int a[MAX];
char cn[MAX];
int f[MAX][8], p[MAX][8], hi[MAX];
ll ans = 1;

void mktbl(int ma) {
	int i, j, k, m;
	for (j = 2; j <= ma; j+=2) {
		i = j, k = 0; while (!(i & 1)) k++, i >>= 1;
		f[j][hi[j]] = 2, p[j][hi[j]++] = k;
	}
	for (m = 3; m <= ma; m += 2) if (!cn[m]) {
		f[m][hi[m]] = m, p[m][hi[m]++] = 1;
		for (j = m << 1; j <= ma; j += m) {
			cn[j] = 1;
			i = j, k = 0; while (i % m == 0) i /= m, k++;
			f[j][hi[j]] = m, p[j][hi[j]++] = k;
		}
	}
  }

int pow_mod(int x, int p) {
	int r = 1; while (p) {
		if (p & 1) r = (ll)r * x % mod;
		x = (ll)x * x % mod;
		p >>= 1;
	}
	return r;
}

inline static void mul_pow(int a) { ans = ans * a % mod; }
inline static void chmax(int *a, int b) { if (*a < b) *a = b; }

void reg(int x, int y) {
	int i = 0, j = 0;
	while (i < hi[x] && j < hi[y]) {
		if (f[x][i] < f[y][j]) chmax(a+f[x][i], p[x][i]), ++i;
		else if (f[x][i] > f[y][j]) chmax(a+f[y][j], p[y][j]), ++j;
		else chmax(a+f[x][i], p[x][i]+p[y][j]), ++i, ++j;
	}
	while (i < hi[x]) chmax(a+f[x][i], p[x][i]), ++i;
	while (j < hi[y]) chmax(a+f[y][j], p[y][j]), ++j;
}

int main()
{
	int N, i, j;

	scanf("%d", &N);
	mktbl(N-1);
/*
for (i = 2; i <= 40; ++i) {
	printf("[%d] sz=%d: ", i, hi[i]);
	for (j = 0; j < hi[i]; ++j) printf("(%d,%d) ", f[i][j],p[i][j]);
	printf("\n");
}
*/
	for (i = 1, j = N-1; i <= j; ++i, --j) reg(i, j);
	if (a[2]) mul_pow(pow_mod(2, a[2]));
	for (i = 3; i < N; i+=2) if (a[i])
		mul_pow(pow_mod(i, a[i]));
	printf("%d\n", (int)ans);
	return 0;
}
0