首先经过读题，我们发现找到合格的金坷垃，怎么样的金坷垃才是合格的呢？（我们不难发现1肯定是合格的【题目已经给出了】）

然后我们开始手推一下之后合格的金坷垃：

2-1=1（合格）

3-1-1=1（不合格（1重复减了））

4-2-1=1（合格）

......

对于任意一个数，他减去他的任意一个约数（除它本身）最小值都为他本身的1/2，我们可以考虑倒着推回去这样就行了，发现合格的金坷垃必须是2的倍数，我们可以用反证法来证明，如果一个合格的金坷垃不是二的倍数，那么最后经过前面的相减肯定会变成一个质数。

一个质数的约数（除它本身）只有1，但我们用一个数只能用一次，那么这个金坷垃就不是一个合格的金坷垃

如90：

90-45=45；

45-15=30；

30-10=20；

20-5=15；

15-3=12；

12-6=6；

6-3=3；

最后剩下了3（质数）【这个各位可以自己推一下】

1；

1+1=2；

1+1+2=4；

1+1+2+4=8；

1+1+2+4+8=16；

......

不难发现第i个合格的金坷垃就是2的i-1次方，这样我们就可以用快速幂来解决了

直接用快速幂模板就能过了！

#include<bits/stdc++.h>//万能头

using namespace std;

const int mod=123456789;//要mod的值

long long n;

long long qmi(long long x,long long k){//快速幂模板

    long long res=1;

    while(k>0){

        if(k&1){

            res=res*x%mod;

        }

        x=x*x%mod;

        k>>=1;

    }

    return res;

}

int main(){

    cin>>n;

    cout<<(qmi(2,n-1)%mod+mod)%mod<<endl;//输出2的n-1次方，(qmi(2,n-1)%mod+mod)%mod是防负数的，但这个没有负数就可以不用写

    return 0;//结束程序

}

根据这个题目我们可以引出快速幂了：

顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。这就可以让我们不用担心t掉了。

int qmi(int m, int k, int p)

{

    int ans = 1 % p, t = m;

    while (k)

    {

        if (k&1) ans = ans * t % p;//如果指数是奇数的话，ans=ans*底数t

        t = t * t % p;//底数平方（无论指数是奇数还是偶数都要平方）

        k >>= 1;//指数右移一位（除以2或者向下取整） 
　　} 
　　return res;
}