結果

問題 No.2940 Sigma Sigma Div Floor Problem
コンテスト
ユーザー highlighter
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0