题目

Description

　　给出一个整数 ，你可以对 进行两种操作。

　　1、将x变成4x+3

　　2、将x变成8x+7

　　问，最少通过多少次操作，使得x是1000000007的倍数？

 

Input

　　一行，一个整数x(1<=x<=1000000006)。

Output

　　一行，表示最少的操作步数。保证答案不超过10^5。

 

Sample Input

【样例输入1】125000000【样例输出1】1【样例输入2】281250001【样例输出2】2【样例输入3】18426114【样例输出3】58【样例输入4】705616876【样例输出4】100000

Sample Output

 

 

Data Constraint

 

 

Hint

【数据约定】

对于50%的数据，答案不超过10

对于80%的数据，答案不超过1000

对于100%的数据，答案不超过100000

 

分析

 

•  设原数为n
• 4n+3= n<<2+3(11)相当于在原数上末尾添加两个一
• 8n+7= n<<3+7(111) 相当于在原数上加三个一
• 所以 我们直接每次加末尾一个一
• 直接枚举到能mo为止
• 记得加1以后还要mo哦

 

代码

1 #include
     
       2 #define mo 1000000007 3 using namespace std; 4 int find(long long x) 5 { 6     int ans=0; 7     while (x) 8     { 9         x-=x&(-x);10         ans++;11     }12     return ans;13 }14 int main ()15 {16     long long n;17     cin>>n;18     int ans=0;19     int cha=0;20     while (n%mo!=0)21     {22         n<<=1;23         n+=1;24         n%=mo;25         cha++;26     }27     if ((cha%3)==1)28         ans+=cha/3+1;29     else if ((cha%3)==0)30        ans+=cha/3;31     else if ((cha%3)==2)32        ans+=cha/3+1;33     cout<