1.题目描述：点击打开链接
2.解题思路：本题要求找至少两个整数，使得它们的最小公倍数是n。本题看似简单，，但还是应该注意细节，考虑周密。当n=1时答案是2，当n只有一种素因子时答案是n+1，由于n的最大范围是2^31-1，因此保险起见用long long防止溢出。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;typedef long long LL;const int maxn = 1000000;int vis[maxn];int e[maxn];vector<LL>primes;void init(){int m = sqrt(maxn + 0.5);for (int i = 2; i <= m;i++)if (!vis[i])for (int j = i*i; j <= maxn; j+=i)vis[j] = 1;for (int i = 2; i <= maxn;i++)if (!vis[i])primes.push_back(i);}bool is_prime(LL n){if (n <= maxn){if (!vis[n])return true;else return false;}int m = sqrt((double)n + 0.5);for (int i = 0; i < primes.size(); i++){if (primes[i]>m)break;if (n%primes[i] == 0)return false;}return true;}void solve(LL n){LL tmp = n;int cnt = 0;for (int i = 0; i < primes.size(); i++){int ok = 0;while (tmp%primes[i] == 0){ok = 1;tmp /= primes[i];e[i]++;}if (ok)cnt++;}if (cnt == 1)cout << n + 1 << endl;else if (cnt > 1){LL sum = 0;for (int i = 0; i <= maxn;i++)if (e[i] > 0)sum += pow(primes[i], e[i]);cout << sum << endl;}}int main(){//freopen("test.txt", "r", stdin);LL n;int rnd = 0;init();while (scanf("%lld", &n) != EOF&&n){memset(e, 0, sizeof(e));printf("Case %d: ", ++rnd);if (n == 1)cout << 2 << endl;else{if (n <= maxn&&!vis[n])cout << n + 1 << endl;bool ok = is_prime(n);if (n > maxn&&ok)cout << n + 1 << endl;if (!ok)solve(n);}}return 0;}
当你能梦的时候就不要放弃梦
