SRM478 Div1 Easy(250), Div2 Medium(500) CarrotJumping

CarrotJumping

4(8x+7)+3 = 8(4x+3)+7 = 32x+31
であることから、4xジャンプと8xジャンプの順番に意味は無い。また、4xジャンプをk回したあとの位置は、
4(4(4(…(4x+3)…)+3)+3)+3 = 4^kx+3(4^k-1+4^k-2+…+1) = 4^kx+3(4^k-1)/3 = 4^k(x+1)-1、
8xジャンプをk回したあとは、
8^k(k+1)-1。
3回の4xジャンプと2回の8xジャンプは同じ位置に行くので、4xジャンプは高々2回。

#include <vector>

using namespace std;

class CarrotJumping
{
public:
    int theJump( int init );
};

int CarrotJumping::theJump( int init )
{
    const int M = 1000000007;

    vector<long long> p4(1,1), p8(1,1);     //  4^i, 8^i

    for ( int s=0; s<=100000; s++ )
    {
        for ( int s4=0; s4<=min(2,s); s4++ )
            if ( ( p8[s-s4]*p4[s4]%M*(init+1)+M-1 )%M == 0 )
                return s;

        p4.push_back( p4[s] * 4 % M ),
        p8.push_back( p8[s] * 8 % M );
    }

    return -1;
}

追記：
他の方のブログを観ていて、4x+3は2x+1を2回、8x+7は2x+1を3回と考えれば良いと知った。なるほど。あと、4xと8xの合計が小さいものから調べていたけれど、8xが小さいものからでも問題無い。

#include <vector>

using namespace std;

class CarrotJumping
{
public:
    int theJump( int init );
};

int CarrotJumping::theJump( int init )
{
    for ( int i=0; i<300000; i++ )
    {
        init = ( 2*init + 1 ) % 1000000007;
        if ( init == 0 )
            return i>0 ? i/3+1 : -1;
    }

    return -1;
}