【贪心+数论】TypeDB Forces 2023 (Div. 1 + Div. 2, Rated, Prizes!) B. Number Factorization

约定不等于承诺〃 2024-03-22 12:12 13阅读 0赞

[Problem - B - Codeforces][]

题意：

![84a3540a09154230a1f42941fc76a8fe.png][]

思路：

把我CPU干烧了

看看别人的题解：

![b3f20e6d0d484acdab76115f29131f43.png][]

![9721e4ec4c984d10815b64280273ceae.png][]

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=3e5+10;
    
    vector<pair<int,int> > v;
    
    int N;
    
    void solve(){
    	v.clear();
    	cin>>N;
    	for(int i=2;i<=N/i;i++){
    		if(N%i==0){
    			int s=0;
    			while(N%i==0) N/=i,s++;
    			v.push_back({i,s});
    		}
    	}
    	if(N>1) v.push_back({N,1});
    	int ans=0;
    	while(v.size()){
    		int res=1;
    		vector<pair<int,int> > tmp;
    		for(auto it:v){
    			res*=it.first;
    			if(--it.second) tmp.push_back({it.first,it.second});
    		}
    		ans+=res;
    		v=tmp;
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - B - Codeforces]: https://codeforces.com/contest/1787/problem/B
[84a3540a09154230a1f42941fc76a8fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/1909bad773324b4e88103864eefe3707.png
[b3f20e6d0d484acdab76115f29131f43.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/1515812c7bab4dd5b1a9c7210ecb7cb4.png
[9721e4ec4c984d10815b64280273ceae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/6f60fc031aa94b09976bf595f05192a5.png