SRM 664 DIV1 Easy - BearPlays

問題


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は大きいので繰り返し2乗法を用いる。

コード


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);
}

};

Share this

Related Posts

Previous
Next Post »