[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]
Recent Comments