結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー sig_256
提出日時 2026-04-19 16:09:05
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,432 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,975 ms
コンパイル使用メモリ 96,752 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-19 16:09:14
合計ジャッジ時間 3,703 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
#include <utility>

long long mod = 998244353;

std::vector<long long> cnts, base;
inline void update_cnts(const int& offset) {
	cnts[offset] ++;
	for (int i = offset; i >= 2; --i) {
		base[i] = base[i + 1] * cnts[i] % mod;
	}
}

long long umekomi[] = {0,872119937,184731056,536258375,456354121,550802483,73077724,91962779,207852605,918265207,29123438,906255998,396523343,886569066,424057750,981950439,94206159,45873866,873888377,552849124,993098840,400650089,743805257,352995645,608410085,719627934,56774200,747875179,8035792,820079823,94944489,512093040,648240604,501507482,558349918,92690251,127320633,263753506,804866913,958472276,564609841,987426557,223358902,749795443,12724417,724448882,817059102,352560524,960632598,71459147,995836333,81864437,530978342,429527426,938548310,706754321,154026105,648291121,11404346,276585524,651821256,892768857,908202394,806572817,95972266,924293584,710321492,292409656,390720978,748535055,432077968,633259931,611457227,106157729,208765272,485550660,535656405,676750021,882686785,902204241,641481866,251117764,243254134,797000068,134549313,959976222,778282973,326116959,22385712,24306820,494058901,848346992,249319915,587021300,221630052,241854233,145374972,117780790,388913189,749891425,529410216};

int main() {
	base = cnts = std::vector<long long>(62, 1);
	cnts[2] = -1;
	long long N;
	std::cin >> N;
	long long sN = std::sqrt(N);
	long long u_size = 10000000;
	long long u_i = sN / 10000000;
	long long s = u_i * u_size;
	long long l = (s - 1) * (s - 1);
	long long lm = l % mod;
	long long n = s * s;
	long long nm = n % mod;
	long long m, mm;
	long long ans = umekomi[u_i];
	cnts[2] = s - 1;
	std::priority_queue<
		std::pair<long long, int>,
		std::vector<std::pair<long long, int>>,
		std::greater<std::pair<long long, int>>
	> que;
	for (long long p = 3; p < 61; ++p) {
		long long b = 2;
		while (true) {
			bool flag = true;
			long long b_p = b;
			for (long long q = 1; q < p; ++q) {
				if (N / b_p < b) {
					flag = false;
					break;
				}
				b_p *= b;
			}
			if (flag) {
				if (b_p >= n) {
					que.emplace(b_p, p);
				} else {
					cnts[p] ++;
				}
			} else break;
			b ++;
		}
	}
	for (int i = 60; i >= 2; --i) {
		base[i] = base[i + 1] * cnts[i] % mod;
	}
	/*long long t = 0;
	for (long long n = 1; n <= sN; ++n) {
		long long nm = n % mod;
		t += nm * nm % mod;
		if (t >= mod) t -= mod;
	}
	std::clog << t << '\n';
	return 0;*/
	while(s <= sN) {
		ans += nm * (nm - 1) / 2 % mod * base[2] % mod;
		ans -= lm * (lm - 1) / 2 % mod * base[2] % mod;
		if (ans < 0) ans += mod;
		else if (ans >= mod) ans -= mod;
		l = n;
		lm = nm;
		update_cnts(2);
		while (!que.empty() && que.top().first == n) {
			update_cnts(que.top().second);
			que.pop();
		}
		s ++;
		n = s * s;
		nm = n % mod;
		while (!que.empty() && que.top().first < n) {
			m = que.top().first;
			mm = m % mod;
			ans += mm * (mm - 1) / 2 % mod * base[2] % mod;
			ans -= lm * (lm - 1) / 2 % mod * base[2] % mod;
			if (ans < 0) ans += mod;
			else if (ans >= mod) ans -= mod;
			l = n;
			lm = nm;
			while (!que.empty() && que.top().first == m) {
				update_cnts(que.top().second);
				que.pop();
			}
		}
	}
	long long Nm = N % mod;
	ans += (Nm + 1) * Nm / 2 % mod * base[2] % mod;
	ans -= lm * (lm - 1) / 2 % mod * base[2] % mod;
	if (ans < 0) ans += mod;
	else if (ans >= mod) ans -= mod;
	std::cout << ans << std::endl;
}
0