2007 - 蹦蹦跳跳的Rabbit大神

关于兔子~蹦蹦跳跳的兔子~谨以此题膜拜Rabbit大神。

话说小兔兔跳得很远，如果他处于位置x，则他能跳到4x+3或8x+7的位置，但是由于环境不好，只有%1,000,000,007=0的位置才有草。

但是小兔兔很饿，他最多只能跳100,000次，问，他最少需要跳几次才能吃到草？

如果他吃不到草，输出-1。

假设小兔兔的位置是281250001，则他先跳到1125000007（4x+3），再跳到9000000063(8x+7)。9000000063=9*1000000007。所以需要跳两次。

Input

一个数x，表示小兔兔的位置，n<1,000,000,007

Output

一个数，最少跳的次数，如果在规定步数内吃不到草输出-1.

Examples

Input

125000000
281250001

Output

1
2

Solution C

#include<stdio.h>

const int maxn=1000000007;

int main(void)
{
    long long x, m;
    int cnt;
    int temp;
    while(scanf("%lld", &m)!=EOF){
        cnt=0; temp=0;
        x=m;
    for(int i=0; i<=100000; i++)
    {
        if(x%maxn==0)
        {
            temp=1;
            break;
        }
        else
        {
            x=(8*x+7)%maxn;
            cnt++;
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        cnt++;
        for(int i=1; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        x=(4*x+3)%maxn;
        cnt+=2;
        for(int i=2; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    printf("-1\n");
    else
    printf("%d\n", cnt);
}
    return 0;
}

Solution C++

#include<stdio.h>

const int maxn=1000000007;

int main(void)
{
    long long x, m;
    int cnt;
    int temp;
    while(scanf("%lld", &m)!=EOF){
        cnt=0; temp=0;
        x=m;
    for(int i=0; i<=100000; i++)
    {
        if(x%maxn==0)
        {
            temp=1;
            break;
        }
        else
        {
            x=(8*x+7)%maxn;
            cnt++;
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        cnt++;
        for(int i=1; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    {
        x=m;
        cnt=0;
        x=(4*x+3)%maxn;
        x=(4*x+3)%maxn;
        cnt+=2;
        for(int i=2; i<=100000; i++)
        {
            if(x%maxn==0)
            {
                temp=1;
                break;
            }
            else
            {
                x=(8*x+7)%maxn;
                cnt++;
            }
        }
    }
    if(temp==0)
    printf("-1\n");
    else
    printf("%d\n", cnt);
}
    return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题