首先经过读题，我们发现找到合格的金坷垃，怎么样的金坷垃才是合格的呢？（我们不难发现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掉了。
快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。（一般在题目当中都会mod一个数字，我们也不用考虑写高精度）
让我们先来看一个简单的例子：
我们用ans来记录答案
因为这个是乘法，所以说ans赋值为1；
3^10=3*3*3*3*3*3*3*3*3*3*ans
3^10=(3*3)*(3*3)*(3*3)*(3*3)*(3*3)*ans
3^10=(3*3)^5*ans；
3^10=9^5
—————– 一次操作（n为偶数的情况）（n为偶数的情况，ans的值不会改变）
3^10=（9^4）* 9
ans=ans*9；
3^10= (9^4)*ans
9^5= （81^2）*ans
—————– 又一次操作（n为奇数的情况）（n为奇数的情况，ans的值等于它本身×底数）
所以在实现代码之前，我们先在这里总结一下快速幂
- 优势：
- 时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高
- 用法：
- 指数为奇数，ans=ans*底数，底数平方，指数右移一位（除以2向下取整）
- 指数为偶数，ans不变，底数平方，指数右移一位（除以2）
代码实现
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;
}
