SRM 672 DIV1 Easy - Procrastination

問題

http://community.topcoder.com/stat?c=problem_statement&pm=14072&rd=16552

解き方

素数を考えると、素数自身は交換対象とならない。
よって、何度交換が発生しても、ｎはｎより小さい素数とｎより大きい素数の
間に収まる。

素数の間隔は６００以内におさまるので、その間の全ての数の約数を調べて
シミュレーションし、最終的なｎの収束点が答えになる。

コード

class Procrastination {

public: long long findFinalAssignee(long long n) {
long long L=max(2LL,n-600),R=n+600;

set<long long> s;
for(long long i=L;i<=R;i++){
for(long long j=2;j*j<=i;j++){
if(i%j==0){
s.insert(j);
s.insert(i/j);
}
}
}

vector<long long> vx;
for(set<long long>::iterator it=s.begin();it!=s.end();it++){
vx.push_back(*it);
}
sort(all(vx));

FORE(i,0,vx.size()){
if((n-1)%vx[i]==0 && n-1>vx[i])n--;
else if(n%vx[i]==0 && n>vx[i])n++;
}

return n;
}

};

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

コード

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

};

SRM 537 DIV1 Easy - KingXNewCurrency

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11817&rd=14730

解き方

A，B自身をXとYで表せられるような整数を求めれば良い。
どちらもXで割り切れるならばYが不要になるので−１となる。

コード

class KingXNewCurrency {

public: int howMany(int A, int B, int X) {
if(A%X==0 && B%X==0)return -1;

set<int> s1,s2;
for(int i=0;i<A;i+=X)for(int j=1;j<=A-i;j++){
if((A-i)%j==0)s1.insert(j);
}
for(int i=0;i<B;i+=X)for(int j=1;j<=B-i;j++){
if((B-i)%j==0)s2.insert(j);
}

if(A%X==0)return s2.size();
if(B%X==0)return s1.size();

int ret=0;
for(set<int>::iterator it=s1.begin();it!=s1.end();it++){
if(s2.find(*it)!=s2.end())ret++;
}

return ret;
}

};

数学Aの順列（１）

プログラムで場合の数の問題がしばしば出てくるので
数学の順列の問題の解き方整理。

（１）ある場合の数からある条件を含まない場合を求めたいときは
　　　それぞれの場合の数をもとめて集合の排他を計算する。

　　（例）０，１，２，４を並べて４ケタの数をつくる　＝４！－３！

（２）a<b<c<dからa,b,c,dを選ぶ場合の数はC,組み合わせ順列に帰着できる。
　　逆にこの形に変換できれば組み合わせ順列の適用が可能。

　　（例）１～９の数字から重複を許して４回数字を選び、
　　　　　その数字がa<b<c<dとなるようにする

（３）人を一列に並べるなど、人を扱う順列の場合は区別するのでPで計算する。

　　　（例）男子５人、女子３人を一列に並べる

（４）隣り合う場合はそのパターンを一つとみなす、
　　隣り合わない場合はその他の要素の間に入れる

　　（例）AさんとBさんは隣り合う→「AB」を一人とみなす
　　（例）男子が隣り合わない→女子の間に入れる

（５）単純な順列計算ができないときは場合分けを行う。
　　かつ、その中で重複がないようにする。
　
　　（例）１～４の数字から重複を許して５回数字を選び５ケタの数字を作る。
　　　　　このうち１２の並びとなる場合の数を求める。