SRM508 Div1 Easy(250), Div2 Medium(500) DivideAndShift

TopCoder

DivideAndShift

シフトはいつ行っても良い。Nの約数wについて幅をwにしてからシフトを行うとすると、幅をwにするためにN/wの素因数の個数の回数分割が必要で、シフトにmin((M+w-1)%w,w-(M+w-1)%w)回かかる。

#include <algorithm>
using namespace std;

class DivideAndShift{public:
int getLeast( int N, int M )
{
    int ans = N;

    for ( int i=1; i<=N; i++ )
    if ( N%i == 0 )
    {
        //  iの素因数の個数
        int t = i;
        int f = 0;
        for ( int j=2; t>1; j++ )
            while( t%j == 0 )
                t/=j, f++;

        int w = N/i;
        ans = min( ans, f+min((M+w-1)%w,w-(M+w-1)%w) );
    }

    return ans;
}};