自动搬运

查看原文

来自洛谷，原作者为

	π酱 这个家伙AFO了，什么也没有留下

搬运于2025-08-24 22:06:25，当前版本为作者最后更新于2018-11-14 07:09:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先看题目，模拟？DP？1e18不是开玩笑的，外加读入那么短，肯定会想到数论。

（本题解中不是2的次方的数用“非2方数”代替，是2的次方的数用“2方数”代替）

做法0

打表，打这么个20个就能发现只有1、2、4、8、16满足了， 再用$2^{k-1}$的快速幂轻松解决

（啥？不会快速幂？你是来考$NOIP$的吗？）

做法1

倒推1（可以这样蒙蔽你自己）

想要最后得到1，那么必然存在一个数$i$，使得$i$减去它的一个因数得到$1$，那么满足条件的只有2了，同理可推得只有4满足，又因为不能重复跳相同的高度

所以就有了1、2、4、8、16向上不断加的过程。

做法2

倒推2（正解）

我们可以肯定2的次方必然满足要求（一遍一遍减去一半就行），不好验证的就是剩下的数。

对于任意一个2的次方，它只是1、2、4、8...的倍数。也就是说，它不是任何一个非2方数的倍数，那么它加上这个非2方数后，也不是这个数的倍数。

根据题中规则，对于一个深度，只能跳它的因数的深度，且用过的深度不能再用，那么对于任意一个 2方数+非2方数，它一定不是这个非2方数的倍数，也就不能通过减掉这个非2方数来达到2的次方的状态。

同理，对于一个2方数+另一个2方数（2个数不等），你减一个非2方数肯定达不到2的次方的状态，转入上一段所描述的状态。

然后这个两个数的和一定是其中较小2方数的倍数（不解释），那么你需要减去这个较小数以达到2的次方的状态。

如果你减去了这个较小2方数（重点来了！），那么你在这个大的2方数不断减成1的过程中一定需要再减一遍这个较小的2方数！

用8+4举例，为12。已经知道减3、6都不会到达1（看第3段），减去2又不是2方数（10），所以减4。但8往下减小会用到一次4！所以一个2方数+另一个2方数的情况也无法满足。

2方数+另一个2方数 和 2方数+非2方数已经表示了除2方数以外的所有数，这两种情况都是不行的，所以只有2的次方满足要求。（手都打累了~）

最后k<=1e18，记得用快速幂。

代码如下（短死了~~~）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=123456789;
int k;

ll pow(int x,int k){
    int x1=1;
    for(;k;k>>=1,x=1ll*x*x%mod)
        if(k&1!=0)
            x1=1ll*x1*x%mod;
    return x1;
}

int main(){
    cin>>k;
    cout<<pow(2,k-1)<<endl;
    return 0;
}