結果

問題 No.3505 Sum of Prod of Root
コンテスト
ユーザー Ryan Shaw
提出日時 2026-04-17 22:03:17
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,130 ms / 2,000 ms
コード長 3,213 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,036 ms
コンパイル使用メモリ 273,268 KB
実行使用メモリ 27,772 KB
最終ジャッジ日時 2026-04-17 22:03:35
合計ジャッジ時間 8,676 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void initcatalan(long long int)':
main.cpp:87:59: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
   87 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                                                   ~~~~~~~~^
main.cpp:87:24: note: within this loop
   87 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                       ~^~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream> 
using namespace std;

#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

const int MOD = 998244353;//
const int FACTMAX = 2000005;//
const int CATALANMAX = 1000005;//
const int MAXA = 1000005;

int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX];
int smallinv[MAXA];

int expo(int a, int b){
	int res=1;
	a%=MOD;
	while (b){
		if (b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

int inv(int num){
	return expo(num, MOD-2);
}

void initfact(){
	fact[0]=1;
	for (int i=1; i<FACTMAX; ++i)fact[i]=(fact[i-1]*i)%MOD;
	invfact[FACTMAX-1]=inv(fact[FACTMAX-1]);
	for (int i=FACTMAX-2; i>=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD;
}
 
int ncr(int n, int r){
	if (n<r||r<0)return 0;
	return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD;
}

int gcd(int a, int b){
	while (b){
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}

int lcm(int a, int b){
	int temp=gcd(a, b);
	a/=temp;
	b/=temp;
	return a*b*temp;
}

void initcatalan(int k){
	cat[0]=1;
	for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
}

int pw(int a, int k, int lim){
	int x=1;
	while (k--){
		if (x>lim/a)return lim+1;
		x*=a;
	}
	return x;
}

int isqrt(int x){
	int r=sqrtl((long double)x);
	while ((r+1)<=x/(r+1))++r;
	while (r>x/r)--r;
	return r;
}

int sum2(int n){
	n%=MOD;
	return (((n*(n+1))%MOD)*((2*n+1)%MOD))%MOD*inv(6)%MOD;
}

int sum3(int n){
	n%=MOD;
	int s=((n*(n+1))%MOD)*inv(2)%MOD;
	return (s*s)%MOD;
}

int sum4(int n){
	n%=MOD;
	int t1=(n*(n+1))%MOD;
	int t2=(2*n+1)%MOD;
	int t3=(3*n%MOD*n%MOD+3*n-1+MOD)%MOD;
	return (((t1*t2)%MOD)*t3)%MOD*inv(30)%MOD;
}

int sumrange(int l, int r){
	if (l>r)return 0;
	return (((l+r)%MOD)*((r-l+1)%MOD))%MOD*inv(2)%MOD;
}

int pref(int x){
	if (x<=0)return 0;
	int m=isqrt(x);
	int n=m-1;
	int full=(2*sum4(n)+3*sum3(n)+sum2(n))%MOD;
	int tail=(m%MOD)*sumrange(m*m, x)%MOD;
	return (full+tail)%MOD;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for (int i=1; i<MAXA; ++i){
		if (i==1)smallinv[i]=1;
		else smallinv[i]=MOD-(MOD/i)*smallinv[MOD%i]%MOD;
	}
	int t=1;
	//cin>>t;
	while (t--){
		int n;
		cin>>n;
		vector<pii> ev;
		for (int k=3; k<=60; ++k)for (int a=2; ; ++a){
			int x=pw(a, k, n);
			if (x>n)break;
			ev.pb({x, a});
		}
		sort(ev.begin(), ev.end());
		int cur=1, h=1, ans=0, i=0;
		while (i<ev.size()){
			int x=ev[i].fi;
			if (cur<x){
				int add=(pref(x-1)-pref(cur-1)+MOD)%MOD;
				ans=(ans+h*add)%MOD;
			}
			int mul=1;
			while (i<ev.size()&&ev[i].fi==x){
				int a=ev[i].se;
				mul=mul*a%MOD*smallinv[a-1]%MOD;
				++i;
			}
			h=h*mul%MOD;
			cur=x;
		}
		if (cur<=n){
			int add=(pref(n)-pref(cur-1)+MOD)%MOD;
			ans=(ans+h*add)%MOD;
		}
		cout<<ans<<"\n";
	}
}
0