SRM 599 DIV1 Easy - BigFatInteger (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12867&rd=15711
・最初は１から始まり、Ａ＾Ｂとなる数にしたい。
・操作方法は、素数をかけるか、現在の数の約数をかけるかの２通り。
このとき、最小の操作回数を求める。
解き方
サンプルを例に素因数分解してみる。
Ａ＝360、Ｂ＝8のとき、
Ａ＝2＾3＋3＾2＋5
Ａ＾Ｂ＝2＾24＋3^16＋5＾8
ここで、最も大きい階乗２４に対して2^K>=24となるＫを考えた時
素因数の数＋Ｋが答えになることがわかる。
コード
class BigFatInteger {
public: int minOperations(int A, int B) {
int x0=0;
int x1=0;
for(int i=2;i<=A;i++){
int cnt=0;
while(A%i==0){
A/=i;
cnt++;
}
if(cnt==0)continue;
x0++;
cnt*=B;
int p=1,tmp=0;
while(p<cnt){
p*=2;
tmp++;
}
x1=max(x1,tmp);
}
return x0+x1;
}
};
public: int minOperations(int A, int B) {
int x0=0;
int x1=0;
for(int i=2;i<=A;i++){
int cnt=0;
while(A%i==0){
A/=i;
cnt++;
}
if(cnt==0)continue;
x0++;
cnt*=B;
int p=1,tmp=0;
while(p<cnt){
p*=2;
tmp++;
}
x1=max(x1,tmp);
}
return x0+x1;
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BigFatInteger {
public: int minOperations(int A, int B) {
int ret=0,cnt=0;
for(int i=2;i<=A;i++)if(A%i==0){
ret++;
int tmp=0;
while(A%i==0)A/=i,tmp++;
cnt=max(cnt,tmp);
}
if(!(cnt==1 && B==1)){
cnt*=B;
for(int i=1;;i++)if(cnt<=pow(2,i)){
ret+=i;
break;
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class BigFatInteger {
public: int minOperations(int A, int B) {
int ret=0,cnt=0;
for(int i=2;i<=A;i++)if(A%i==0){
ret++;
int tmp=0;
while(A%i==0)A/=i,tmp++;
cnt=max(cnt,tmp);
}
if(!(cnt==1 && B==1)){
cnt*=B;
for(int i=1;;i++)if(cnt<=pow(2,i)){
ret+=i;
break;
}
}
return ret;
}
};
