問題
http://community.topcoder.com/stat?c=problem_statement&pm=13916&rd=16513
解き方
数学的に解くことができるのに気がつけるか。
A+B=Sとすると、
A<Bのとき、A=2*A=2A%S
A>Bのとき、A=A-B=A+(A-(A+B))=A+(A-S)=2A-S=2A%S
よって常にA*2%Sとなる。
K回かけるので、かけた後はA*2^k%Sとなり、この値とSからこの値を引いたもののうち
最小のものが答えになる。
Kは大きいので繰り返し２乗法を用いる。
コード
class BearPlays {
public:
long long modpow(long long a,long long k,long long m){
if(k==0)return 1;
if(k%2==0)return modpow((a*a)%m,k/2,m);
return (a*modpow(a,k-1,m))%m;
}
int pileSize(int A, int B, int K) {
long long a=(A*modpow(2,K,A+B))%(A+B);
return min(a,A+B-a);
}
};
public:
long long modpow(long long a,long long k,long long m){
if(k==0)return 1;
if(k%2==0)return modpow((a*a)%m,k/2,m);
return (a*modpow(a,k-1,m))%m;
}
int pileSize(int A, int B, int K) {
long long a=(A*modpow(2,K,A+B))%(A+B);
return min(a,A+B-a);
}
};
Share this
Related Posts
数学Aの順列（１）
プログラムで場合の数の問題がしばしば出てくるので
数学の順列の問題の解き方整理。
（１）ある場合の数からある条件を含まない場合を求めたいときは
それぞれの場合の数をもとめて集合の排他を計算する。
（例）０，１，２，４を並- SRM 672 DIV1 Easy - Procrastination
問題
http://community.topcoder.com/stat?c=problem_statement&pm=14072&rd=16552
解き方
素数を考えると、素数自身は交換対象とならない
- SRM 537 DIV1 Easy - KingXNewCurrency
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11817&rd=14730
解き方
A，B自身をXとYで表せられるような整数を求