题目链接： https://vjudge.net/problem/UVA-10791
题目描述： 给一个数n, 让你求至少两个数的lcm是n 的， 最小和
解题思路： 唯一分解， 每个单独的素数的幂加起来就是答案
代码：
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cstring> #include <iterator> #include <cmath> #include <algorithm> #include <stack> #include <deque> #include <map> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define mem0(a) memset(a,0,sizeof(a)) #define meminf(a) memset(a,0x3f,sizeof(a)) #define fi(n) for(i=0;i<n;i++) #define fj(m) for(j=0;j<m;j++) #define sca(x) scanf("%d",&x) #define scalld(x) scanf("%I64d",&x) #define print(x) printf("%d ",x) #define printlld(x) printf("%I64d ",x) #define d printf("======= ") typedef long long ll; using namespace std; //const int maxn = 1e6+10; vector< pair<ll, int> > V; vector< pair<ll, int> >::iterator it; void build( ll num ) { ll m = (double)sqrt(num+0.5); // cout << m << endl; for( int i = 2; i <= m; i++ ) { int cnt = 0; while( num % i == 0 ) { num /= i; cnt++; } if( cnt != 0 ) { V.push_back(make_pair(i, cnt)); } } if( num > 1 ) { V.push_back(make_pair(num, 1)); } } //const int INF = 1e11; int main() { ll n; int cases = 1; // for( int i = 0; i < 12; i++ ) { // cout << prime[i] << " "; // } // cout << endl; // cout << cnt << endl; // freopen("in.txt", "r", stdin ); while( cin >> n && n ) { V.clear(); if( n == 1 ) {cout << "Case " << cases++ << ": " << 2 << endl; continue; } build(n); int cnt = (int)V.size(); double res = 0; for( it = V.begin(); it != V.end(); it++ ) { res += pow( double(it->first), double(it->second) ); } if( cnt == 1 ) cout << "Case " << cases++ << ": " << ll(res+1) << endl; else cout << "Case " << cases++ << ": " << ll(res) << endl; } return 0; }
思考： 哎， 我都不想说啥了， 一开始RE了， 是我素数分解的时候不长脑子， 后来我没有特判1， 我还一直以为是自己哪里格式出了毛病， 结果还真得打了一个"#"， 以后做题直接复制粘贴吧， 自己打了一年多了还是改不了马虎的习惯， 真的是是很烦