結果

問題 No.1529 Constant Lcm
コンテスト
ユーザー spipipike
提出日時 2021-06-04 20:37:41
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,220 ms / 3,000 ms
コード長 1,270 bytes
コンパイル時間 2,112 ms
コンパイル使用メモリ 181,264 KB
実行使用メモリ 10,628 KB
最終ジャッジ日時 2024-11-19 09:40:29
合計ジャッジ時間 15,262 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

struct Sieve {
	int n;
	vector<int> f, primes;
	Sieve(int n=1):n(n), f(n+1) {
		f[0] = f[1] = -1;
		for (ll i = 2; i <= n; ++i) {
			if (f[i]) continue;
			primes.push_back(i);
			f[i] = i;
			for (ll j = i*i; j <= n; j += i) {
				if (!f[j]) f[j] = i;
			}
		}
	}
	bool isPrime(int x) { return f[x] == x;}
	vector<int> factorList(int x) {
		vector<int> res;
		while (x != 1) {
			res.push_back(f[x]);
			x /= f[x];
		}
		return res;
	}
	vector<P> factor(int x) {
		vector<int> fl = factorList(x);
		if (fl.size() == 0) return {};
		vector<P> res;
		int pre= -1;
		for (int p : fl) {
			if (pre == p) {
				res.back().second++;
			} else {
				res.emplace_back(p, 1);
			}
			pre=p;
		}
		return res;
	}
};

const int M=998244353;

int main(){
	int n;
	cin>>n;

	Sieve si(n);
	unordered_map<int, int> ma;

	for(int i=1; i<=n-1; i++){
		unordered_map<int, int> lma;
		for(P p : si.factor(i)) lma[p.first]+=p.second;
		for(P p : si.factor(n-i)) lma[p.first]+=p.second;
		for(P p : lma) ma[p.first]=max(ma[p.first], p.second);
	}

	int ans=1;
	for(P p : ma) rep(_, p.second) ans=(ll)ans*(p.first)%M;

	cout<<ans<<endl;
	return 0;
}
0