小昂总是感觉饥饿,所以作为章⻥的小昂经常出去寻找⻉壳吃。最开始小昂在一个初始位置 x 0 。对
于小昂所处的当前位置x,他只能通过神秘的力量移动到 4x + 3 或者 8x + 7 。因为使用神秘力量要
耗费太多体力,所以它只能使用神秘力量最多 k 次。⻉壳总生长位置 z ,位置 y
+ z ,位置 2y + z
等)。小昂需要你帮忙计算最少需要使用多少次神秘力量就能吃到⻉壳。
输入描述:
输入四个整数 x 0 , y, k, z .
x 0 , z, 范围在0 到 y − 1
输出描述:
输出小易最少需要使用神秘力量的次数,如果使用次数使用完还没找到⻉壳,则输出 −1
输入1
1 7 100 0
输出1
1
输入2
2 95 5 0
输出2
2
输入3
55 999 2000 874
输出3
10
数据范围
对于30%的数据,有 k
<= 20
对于100%的数据,有 x 0 < = 1e9, y <= 1e9, k <= 500000, z <= 1e
大部分人第一眼看到这题会想到暴力搜索，但是我们仔细推一下x0可以到达的范围，会发现是2^(i)*xo+2^(i)-1(i!=1)，于是我们只需要从小到大找到一个满足条件的i即可。
然后我们再来考虑怎么通过最少的步数来到达这个i。
我们发现通过题目中给的两种方式一种是i+2，一种是i+3，所以我们很容易的通过贪心来把i分成mod3==0，1，2三种情况，在简单判断一下即可。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define il inline
#define db double
using namespace std;
ll x0,y,z,ci[1500045];
int k;
int main()
{
freopen("hungry.in","r",stdin);
freopen("hungry.out","w",stdout);
cin>>x0>>y>>k>>z;
k*=3;
ci[0]=1;
for(int i=1;i<=k;i++)
ci[i]=(ci[i-1]<<1)%y;
for(int i=2;i<=k;i++)
if((x0*ci[i]%y+ci[i]-1)%y==z)
{
if(i%3==0)
printf("%d
",i/3);
if(i%3==2||i%3==1)
printf("%d
",i/3+1);
return 0;
}
printf("-1
");
return 0;
}