- 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
- 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
#include <bits/stdc++.h> 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<int,int> 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; } |
#include <bits/stdc++.h> 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<int,int> 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; }
Speak Your Mind