yukicoder : No.2902 ZERO!!

言い換えが難しい。
https://yukicoder.me/problems/no/2902

問題

整数Nが与えられる。
2以上の整数bに対し、N!=p(b)*b^e(b)と表現できるとする。
2以上N!以下のbにおけるe(b)の総和を求めよ。

解法

求める値はとなる。

i=1の時を考えると、bはN!の約数ということになる。
N!を素因数分解したときに現れる素数pの個数をf(p)とすると、N!未満のN!の約数の個数はとなる。

iが2以上の場合、bのi乗がN!の約数であるものを数えればよいので、となる。
iは高々O(NlogN)しかないので、素数pとiを総当たりして上記積を数え上げよう。

int N;
const ll mo=998244353;

ll F[1010101];
int vis[1010101];
ll P[2010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	FOR(i,2010000) P[i]=1; 
	for(i=2;i<=N;i++) if(vis[i]==0) {
		for(j=i;j<=N;j+=i) vis[j]=1;
		x=N;
		while(x) {
			x/=i;
			F[i]+=x;
		}
		for(j=1;j<=F[i];j++) P[j]=P[j]*(1+F[i]/j)%mo;
	}
	ll ret=-2010000;
	FOR(i,2010000) ret+=P[i];
	cout<<ret%mo<<endl;
}

まとめ

こういうシンプルな問題設定、どこから手を付けるか迷う。