SRM 427 DIV1 Easy - DesignCalendar （復習○）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10155&rd=13518
１日あたりの日数Ｄと１年あたりの日数Ｙが与えられる。
１年あたりの日数が１日あたりの日数で割り切れるのに必要な年数を求める。
解き方
問題文がとにかく難しい。
要は、必要な年数をＸとすると
（Ｙ＊Ｘ）％Ｄ＝＝０となる最小のＸを求めればよい。
ここでＹ％Ｄ＝aとすると、求めるxは
（例）
a=4,D=6のとき lcd=12 gcd=2となりx=3
a=4,D=14のとき lcd=28 gcd=2となりx=7
つまり、x=D/gcd(a,D)となる。
例外処理として、aが割り切れる場合は答えは１となるのに注意。
コード
#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 DesignCalendar {
public:
int gcd(int a,int b){
if(a%b==0)return b;
return gcd(b,a%b);
}
int shortestPeriod(int dayLength, int yearLength) {
int a=yearLength%dayLength;
return a==0 ? 1 :dayLength/gcd(dayLength,a);
}
};
#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 DesignCalendar {
public:
int gcd(int a,int b){
if(a%b==0)return b;
return gcd(b,a%b);
}
int shortestPeriod(int dayLength, int yearLength) {
int a=yearLength%dayLength;
return a==0 ? 1 :dayLength/gcd(dayLength,a);
}
};
