言い換えが難しい。
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; }
まとめ
こういうシンプルな問題設定、どこから手を付けるか迷う。