ACM – UVa10791 – divide prime

点击量:27

谢天谢地终于过了。
就是求分解质因数后的和,如果是质数那么返回1+n本身。

  1. 一开始直接暴力求两个质因数的情况,铁定不对啊。。
  2. 第二次发现策略有问题,转为使用枚举质因数,然后发现仅仅是质因数LCM有问题啊。。
  3. 第三次没有考虑质数
  4. 第四次没有考虑Case
  5. 第五次不记得了。
  6. 第七次AC,哭了真是。。一定要先分析好题目啊。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <bitset>
using namespace std;
// 大数,内存处理
#define inf 0x3f3f3f3f
#define ll long long int
#define mem(a) memset(a, 0, sizeof(a))
#define memm(a) memset(b, -1, sizeof(b))
#define deb(x, n) cout << (x) << " " << (n) << endl
#define cr printf("\n")
// 调试用
    template <class type>
void debug(type a[], int len)
{
    for(int i = 0; i < len ; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}
ll solve(int n)
{
    if(n == 1) return 2;
    ll ans = 0;
    ll sq = sqrt(n);
    int cnt, pf = 0;
    for(ll i = 2; i <= sq;i++)
    {
        if(n % i == 0)
        {
            cnt = 1;
            while(n % i == 0)
            {
                cnt *= i;
                n /= i;
            }
            pf ++;
            ans += cnt;
        }
    }
    if(1 != n)
    {
        ans += n;
        pf++;
    }
    // n为质数
    if(pf <= 1) ans ++;
    return ans;
}
int main()
{
#ifdef debug
    // freopen("input", "r", stdin);
#endif
    int n;
    int c = 1;
    // const int maxn = pow(2, 31) -1;
    // printf("%d\n", maxn);
    ll ans;
    while(scanf("%d", &n) && n)
    {
        ans = solve(n);
        printf("Case %d: ", c++);
        printf("%lld\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注