listgame – kattis

[mathjax]
[su_accordion][su_accordion]
[su_spoiler title=”Đề bài” open=”yes”]
Có hai người chơi trò chơi với nhau, luật như sau:

• Người thứ nhất chọn một số nguyên dương X
• Người thứ hai tìm các số $Y_1, Y_2, .. Y_k$ sao cho $(Y_1 + 1)(Y_2 + 1)…(Y_k + 1) = X$. Khi đó người chới thứ hai được k điểm

Cho X tìm số điểm tối đa mà người chơi thứ hai có thể đạt

Input:

Số nguyên dương $X$ thỏa mãn $10^3 <= X <= 10^9$

Output:

Duy nhất số K là số điểm tối đa có thể đạt

Sample Input 1 65536
Sample Output 1 16

 

Sample Input 2 127381
Sample Output 2 3

[/su_spoiler]
[su_spoiler title=”Thuật toán”]

• Nếu n là số nguyên tố => Kết quả: 1
• Nếu không thì ta phần tích X thành tích các số nguyên tố => Kết quả: là số các số hạng phân tích được

Ví dụ: 12 = 2 * 2 * 3 => Kết quả: 3

[/su_spoiler]
[su_spoiler title=”Code”]

#include 
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e6+3;

bool prime[MAXN];
int i, j, x, cnt, k, sl[MAXN], nt[MAXN];

void tim_snt() {
    prime[1] = 1;
    int n = trunc(sqrt(oo));
    for(i=2; i<=n; i++) {
        if (!prime[i]) {
            j = i*i;
            while (j <= oo) {
                prime[j] = 1;
                j += i;
            }
        }
    }
    cnt = 0;
    for(i=2; i<=oo; i++) if (!prime[i]) {
        cnt++;
        nt[cnt] = i;
    }
}

void phan_tich() {
    int i = 1;
    while (x > 1) {
        while ((x > 1)&&(x % nt[i] == 0))
        {
            k++;
            x /= nt[i];
        }
        i++;
        if (i > cnt) break;
    }
    if (x > 1) k++;
}

bool ktnt(int x) {
    int n = trunc(sqrt(x));
    FOR(i,2,n) {
        if (x % i == 0) return 0;
    }
    return 1;
}

int main() {
    cin >> x;
    if (ktnt(x)) {
        cout << 1;
        return 0;
    }
    tim_snt();
    phan_tich();
    cout << k;
    return 0;
}

[/su_spoiler]
[/su_accordion]