欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

UVA - 10791 Minimum Sum LCM(质因数分解)

程序员文章站 2022-06-22 08:46:24
题目链接还是我孤陋寡闻了,一开始用素筛,想着怎么也筛不到1e9,然后就GG了,实际上对单个数质因数分解不需要使用素筛,这里就学习一下吧!...

题目链接


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

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

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

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

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

本文地址:https://blog.csdn.net/qq_44691917/article/details/107204809