#1011459 (C++23) No.1781 LCM

提出ソース

結果

問題	No.1781 LCM
ユーザー	shobonvip
提出日時	2024-09-19 00:47:15
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,167 ms / 5,000 ms
コード長	4,148 bytes
コンパイル時間	3,253 ms
コンパイル使用メモリ	261,012 KB
実行使用メモリ	23,036 KB
最終ジャッジ日時	2024-09-19 00:47:37
合計ジャッジ時間	17,049 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	3 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	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	1 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	2 ms 5,376 KB
testcase_16	AC	1 ms 5,376 KB
testcase_17	AC	1 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2,086 ms 22,916 KB
testcase_22	AC	2,055 ms 23,036 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2,167 ms 23,016 KB
testcase_26	AC	2,056 ms 22,916 KB
testcase_27	AC	2,076 ms 22,904 KB
testcase_28	AC	1,697 ms 20,808 KB
testcase_29	AC	479 ms 10,168 KB
testcase_30	AC	456 ms 10,320 KB
testcase_31	AC	2 ms 5,376 KB
testcase_32	AC	1 ms 5,376 KB

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

ソースコード

raw source code

#include<bits/stdc++.h>
using namespace std;

// [floor_sqrt(N)]
// 0 <= N <= 9e18
long long floor_sqrt(long long N) {
	long long ub = 3'000'000'001;
	long long lb = 0;
	while (ub - lb > 1) {
		long long t = (ub + lb) / 2;
		if (t * t <= N) lb = t;
		else ub = t;
	}
	return lb;
}


// Quotients
struct Quotients {
	long long sqrtN;
	long long N;
	long long M;
	std::vector<long long> data;

	Quotients(long long _N): N(_N) {
		sqrtN = floor_sqrt(N);
		data = std::vector<long long>(sqrtN);
		for (int i=1; i<=sqrtN; i++) {
			data[i-1] = i;
		}
		for (int i=sqrtN-1; i>=0; i--){
			if (N / data[i] == data[i]) continue;
			data.emplace_back(N / data[i]);
		}

		M = data.size();
	}

	int size() {
		return M;
	}

	long long operator[](int i) {
		if (i < 0 || i >= M){
			throw std::out_of_range("Index out of range");
		}
		return data[i];
	}

	int ind(long long x) {
		if (x <= sqrtN) return x - 1;
		return M - N / x;
	}

	std::pair<long long, long long> interval(long long v) {
		return std::pair(N / (v+1) + 1, N / v + 1);
	}
};


// Lucy DP
// returns (dp, prime_count)
template <typename T, T (*g)(long long), T (*G)(long long)>
std::pair<std::vector<T>, std::vector<long long>> lucy_dp(long long N) {
	Quotients Q(N);

	int m = Q.size();
	std::vector<T> dp(m);
	std::vector<long long> dp2(m);
	for (int i=0; i<m; i++){
		dp[i] = G(Q[i]) - g(1);
		dp2[i] = Q[i] - 1;
	}


	for (int x=2; x<=Q.sqrtN; x++){
		if (dp2[x-1] > dp2[x-2]) {
			long long border = (long long)x * x;
			for (int i=m-1; i>=0; i--){
				if (Q[i] < border) break;
				int tmpind = Q.ind(Q[i]/x);
				dp[i] -= g(x) * (dp[tmpind] - dp[x-2]);
				dp2[i] -= dp2[tmpind] - dp2[x-2];
			}
		}
	}

	return std::pair(dp, dp2);
}

// enumerate primes <= N
std::vector<long long> enumerate_prime(long long N) {
	std::vector<bool> p(N+1);
	std::vector<long long> ret(0);
	for (long long i=2; i<=N; i++){
		if (p[i]) continue;
		ret.emplace_back(i);
		for (long long j=2*i; j<=N; j+=i){
			p[j] = true;
		}
	}
	return ret;
}


// black algorithm
// recommended for N <= 1e12
template<typename T, T(*f) (long long, long long, long long)>
T black_algorithm(
	std::vector<T> GF,
	long long N
) {
	if (N == 1) return 1;

	Quotients Q(N);

	std::vector<long long> prime_list = enumerate_prime(Q.sqrtN);

	int pm = prime_list.size();

	auto dfs = [&](
		auto self,
		long long num,
		T f_old,
		long long gpf,
		long long c,
		long long num_tamari
	) -> T {

		T ret = 0;

		if (gpf >= 0
		&& num * prime_list[gpf] <= N) {
			ret += f_old * f(prime_list[gpf], c+1, num_tamari * prime_list[gpf]);
			if (num * prime_list[gpf] * prime_list[gpf] <= N){
				ret += self(self,
						num * prime_list[gpf],
						f_old,
						gpf,
						c + 1,
						num_tamari * prime_list[gpf]
					);
			}
		}
		
		if (gpf >= 0){
			int lft = Q.ind(prime_list[gpf]);
			int rgt = Q.ind(N / num);
			if (lft < rgt){
				ret += f_old * f(prime_list[gpf], c, num_tamari) * (GF[rgt] - GF[lft]);
			}
		}else{
			int lft = 0;
			int rgt = Q.ind(N / num);
			if (lft < rgt){
				ret += GF[rgt] - GF[lft];
			}
		}

		for (long long i=gpf+1; i<pm; i++){
			if (num * prime_list[i] <= N
			&& num * prime_list[i] * prime_list[i] <= N) {
				if (gpf >= 0){
					ret += self(self,
							num * prime_list[i],
							f_old * f(prime_list[gpf], c, num_tamari),
							i,
							1,
							prime_list[i]
						);
				}else{
					ret += self(self,
							num * prime_list[i],
							f_old,
							i,
							1,
							prime_list[i]
						);
				}
			}else{
				break;
			}
		}

		return ret;

	};

	return dfs(dfs, 1, 1, -1, 0, 1) + T(1);
}


#include<atcoder/modint>
typedef atcoder::modint998244353 mint;
typedef long long ll;

mint t[60];

mint f(ll p, ll e, ll n) {
	return t[e+1];
}

mint g(ll p) {
	return 1;
}

mint G(ll p){
	return p;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, m; cin >> n >> m;
	for (int i=1; i<60; i++){
		t[i] = mint(i).pow(n);
	}

	auto [a,b] = lucy_dp<mint,g,G>(m);
	vector<mint> x((int)a.size());

	mint tmp = mint(2).pow(n);
	for (int i=0; i<(int)a.size(); i++){
		x[i] = a[i] * tmp;
	}

	mint ans = black_algorithm<mint,f>(x,m);
	cout << ans.val() << '\n'; 
}

yukicoder

結果

テストケース

ソースコード