#663359 (C++14) No.1529 Constant Lcm

• 問題: No.1529 Constant Lcm
• ユーザー: spipipike
• 提出日時: 2021-06-04 20:37:41
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 1,207 ms / 3,000 ms
• コード長: 1,270 bytes
• コンパイル時間: 1,914 ms
• コンパイル使用メモリ: 181,128 KB
• 実行使用メモリ: 10,628 KB
• 最終ジャッジ日時: 2024-04-30 00:09:01
• 合計ジャッジ時間: 14,888 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	4 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	2 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	1,070 ms; 10,264 KB
testcase_11	AC	388 ms; 6,144 KB
testcase_12	AC	20 ms; 5,376 KB
testcase_13	AC	863 ms; 9,184 KB
testcase_14	AC	518 ms; 7,680 KB
testcase_15	AC	573 ms; 7,808 KB
testcase_16	AC	456 ms; 6,528 KB
testcase_17	AC	235 ms; 5,376 KB
testcase_18	AC	239 ms; 5,504 KB
testcase_19	AC	550 ms; 7,680 KB
testcase_20	AC	1,199 ms; 10,628 KB
testcase_21	AC	1,192 ms; 10,500 KB
testcase_22	AC	1,180 ms; 10,496 KB
testcase_23	AC	1,207 ms; 10,496 KB
testcase_24	AC	1,185 ms; 10,496 KB
testcase_25	AC	1,173 ms; 10,500 KB

ソースコード

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