首页 > 代码库 > UVA 10791 Minimum Sum LCM
UVA 10791 Minimum Sum LCM
唯一分解定理
把n分解为 n=a1^p1*a2^p2*...的形式，易得每个ai^pi作为一个单独的整数最优。
坑：
n==1 ans=2；
n因子种数只有一个 ans++；
注意溢出。
1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 typedef long long ll; 6 7 ll ans=0; 8 ll n; 9 ll sign[100000];10 ll pri[100000];11 int tot;12 13 void getpri (){14 memset (sign,0,sizeof sign);15 sign[0]=sign[1]=1;16 for (int i=2;i*i<100000;i++)17 if (!sign[i])18 for (int j=i*i;j<100000;j+=i)19 sign[j]=1;20 tot=0;21 for (int i=2;i<100000;i++)22 if (!sign[i])23 pri[tot++]=i;24 }25 26 ll solved (){27 if (n==1)28 return 2;29 ll ans=0;30 int flag=0;31 for (int i=0;i<tot&&pri[i]*pri[i]<=n;i++){32 ll temp=0;33 if (n%pri[i]==0){34 temp=1;35 flag++;36 while (n%pri[i]==0){37 temp*=pri[i];38 n/=pri[i];39 }40 }41 ans+=temp;42 }43 if (n!=1){44 flag++;45 ans+=n;46 }47 if (flag<=1)48 ans+=1;49 return ans;50 }51 52 int main (){//int a=46341;cout<<a*a<<" "<<(1<<31)<<endl;53 int kase=0;54 getpri ();55 while (cin>>n&&n){56 ans=solved ();57 cout<<"Case "<<++kase<<": "<<ans<<endl;58 }59 return 0;60 }
UVA 10791 Minimum Sum LCM
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。