結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー sig_256
提出日時 2026-04-19 16:25:06
言語 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
結果
AC  
実行時間 295 ms / 2,000 ms
コード長 3,264 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,443 ms
コンパイル使用メモリ 96,848 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-04-19 16:25:14
合計ジャッジ時間 4,107 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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,105349172,926254955,261543273,937541832,469632936,307587738,803011524,871822510,5440149,303748648,791195344,518231357,597104673,828564783,858158011,683097945,297339994,868969663,455198411,504156699,506311326,505416845,596014992,693209139,466427006,898968203,862781154,908593950,756056738,765833005,856386922,355264830,555474583,419005318,550280846,948958281,509038187,429132624,246418588,129547801,159262622,992291176,960269054,562852734,136818140,820309951,549100591,741618263,806755993,135401443,509361030,1671946,226537555,768535505,977537784,811447484,488109382,541165080,621087518,537206429,622552543,372387060,366460669,826100442,193264476,110607580,547867280,479399758,414076546,912396455,808366131,394609354,570958676,423765379,6450874,888708063,471862859,745156446,312242840,618616039,559829629,522582504,359244752,430575199,558016243,487618202,254047428,663467783,530275772,862753316,872176061,512144843,495840250,645403999,21191360,428077676,3423386,499797143,829936469,313198362};

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 / u_size;
	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;
	}
	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 = m;
			lm = mm;
			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