金坷垃

发表于 更新于 分类于 阅读次数：

Luogu P5035 金坷垃 数学题，给出k，求第k个用自身减去除本身的一个因数，重复过程可以得到1的数 我：打表可知，满足的数必为$2^x$（确信 众：数学论证，请 我： 若有$b a$，且$a - b = 1$，可知$a = 2, b = 1$ 进一步，若$b a$，且$a - b = 2$，可知$a = 4, b = 2$ 运用数学归纳法得答案 $Q.E.D$（论 证 有 力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

long long fpow(long long x, long long y, long long z)
{
    long long ans = 1;
    for (; y; y >>= 1) {
        if (y & 1) ans = ans * x % z;
        x = x * x % z;
    }
    return ans;
}

int main()
{
    long long k;
    cin >> k;
    cout << fpow(2LL, k - 1, 123456789LL) << endl;
    return 0;
}