当前位置：首页 > news >正文

UVA - 10791 Minimum Sum LCM（质因数分解）

news 来源：原创 2024/5/4 5:58:54

题目链接

还是我孤陋寡闻了，一开始用素筛，想着怎么也筛不到1e9，然后就GG了，实际上对单个数质因数分解不需要使用素筛，这里就学习一下吧！

从 $2$ 开始，如果含有该质因子则一直除到不含为止，这样相当于含 $2$ 因子的合数都不会再被整除，类似素筛，那么每次就能保证整除的数一定是这个数的质因数

时间复杂度 $O(\sqrt{n})$ ，也就是说可以对单个的小于 $1 e 14$ 的数进行质因数分解

下面代码有一些细节需要注意，尤其是计算过程的溢出

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <bitset>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=1e7+10;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int kase=0,n;
    while(cin>>n && n){
        int m=sqrt(n+0.5),x=n;
        ll ans=0;
        int num=0;
        for(int i=2;i<=m;i++){
            if(n%i==0){
                ll res=1;
                while(n%i==0){
                    n/=i;
                    res*=i;
                }
                ans+=res;
                num++;
            }
            if(n==1) break;
        }
        if(n==x) ans=1LL+n; //因为n是int最大值，所以不能直接n+1会溢出
        else if(n>1) ans+=n;
        else if(n==1 && num==1) ans++;
        cout<<"Case "<<++kase<<": "<<ans<<endl;
    }
    return 0;
}