天哪！毫无思绪！令人感到恐惧的数学(水题?)(TOWQs)

时间：2021-10-15 19:47:44

这道题的题目描述灰常简单，第一眼看以为是一道十分水的题目；

但是！！！（我仔细一看也没有发现这背后隐藏着可怕的真相~）

下面给出题目描述：

给出一个整数x，你可以对x进行两种操作。
1、将x变成4x+3
2、将x变成8x+7
问，最少通过多少次操作，使得x是1000000007的倍数？

没错，就是这么坑！当我仔细读完题目后本还抱有几分希望（也许可以水过）

但是！！！没错我又一次用了“但是”这个词；

当我看到数据范围时我几乎就放弃了，只能用暴力来骗分了，仅仅只水到了50分（也知足了）

【输入格式】

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

【输出格式】

一行，表示最少的操作步数。保证答案不超过10^5。
如此多的可能性，使我敢打赌这绝对是一道数学题，而且是我想不到的那种；真是让人感到没有办法。。

而更加令人吃惊的在后面：我以为这道题应该会用到我所不能触及的只是，然而，只是一个十分巨大的脑洞！

没错，学长仅仅只是在黑板（白板？）上写下了两个式子，如下：

##

8( 8x + 7 ) + 7 = 64x + 63；
4( 4( 4x + 3 ) + 3 ) + 3 = 64x + 63；

然后再稍微的推导一下就可以得到：

2( 2x + 1 ) + 1 = 4x + 3；
2( 2( 2x + 1 ) + 1 ) + 1 = 8x + 7；

真是令人感到吃惊！这意味着 当我们运行了两次 8x+7 运算时，就相当于运行了三次 4x+3 运算；

那么这道题目就变的简单了许多，我们可以得到结论：4x+3的运算次数必然不会达到3次以上，因为如果有三次 4x+3 运算便可以用两次 8x+7 运算来代替(题目要求用尽可能少的次数来解);

而为了方便一些，我们便统一的用 2x+1 来代替这两种运算！

1
2
3
4
5
6
 
while(true)
{
大专栏  天哪！毫无思绪！令人感到恐惧的数学(水题?)(TOWQs)span class="line">    num=(num*2+1)%1000000007;
    ans++;
    if(num==0) break;
}

这就简单了许多，下面就可以上正解的代码了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#include&lt;cstdio&gt;
using namespace std;
long long ans,num;
int ()
{
    scanf("&amp;lld",&amp;n);
    while(true)
    {
        num=(num*2+1)%1000000007;
        ans++;
        if(num==0) break;
    }
    printf("%lldn",(ans-1)/3+1);
    return 0; 
}

相关文章