SRM-427 250pt: DesignCalendar

keyword

整数　C++

問題概要

Y, Dが与えられたときR=Y%Dに対してR*P=0 (mod D)を満たす最小のP(>0)を求める問題。

解法

RとDが互いに素ならP=Dが答えになることは自明。なのでRとDを最大公約数で割ってやる。もちろん問題の読解が一番難しい。

int shortestPeriod(int dayLength, int yearLength) {
    int r = yearLength%dayLength;
    return dayLength/__gcd(dayLength,r);
}