結果
問題 | No.2940 Sigma Sigma Div Floor Problem |
ユーザー |
![]() |
提出日時 | 2024-09-15 21:18:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 886 bytes |
コンパイル時間 | 3,080 ms |
コンパイル使用メモリ | 251,064 KB |
実行使用メモリ | 12,812 KB |
最終ジャッジ日時 | 2024-10-18 20:50:10 |
合計ジャッジ時間 | 8,725 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 WA * 1 |
other | AC * 14 WA * 15 RE * 20 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long struct Eratosthenes{ vector<bool> isprime; vector<int> minfactor; Eratosthenes(int N) : isprime(N+1,true),minfactor(N+1,-1) { isprime[1]=false; minfactor[1]=1; for(int p=2;p<=N;p++) { if(!isprime[p]) continue; minfactor[p]=p; for (int q=p*2;q<=N;q+=p){ isprime[q]=false; if(minfactor[q]==-1) minfactor[q]=p; } } } vector<pair<int,int>> factorize(int n){ vector<pair<int,int>> res; while(n>1){ int p=minfactor[n]; int exp=0; while(minfactor[n]==p) { n/=p; exp++; } res.emplace_back(p,exp); } return res; } }; signed main(){ int N; cin >> N; int ans=0; Eratosthenes er(N+1); for(int i=1;i<=N;i++){ vector<pair<int,int>> vec=er.factorize(i); int res=1; for(auto i : vec){ res*=i.second+1; } ans+=res*(N-i+1); } cout << ans << endl; }