HDU5478-Can you find it

题目大意

有一个对于一个有序数对 $(a, b)$ 和 $k 1, k 2, b 1$ ，要求满足等式 $a^{k 1 \cdot n + b 1} + b^{k 2 \cdot n - k 2 + 1} \equiv 0 (m o d C) (\forall n = 1, 2, 3, . . .)$

问这样的a,b 有多少对？以字典序输出。

分析

当n=1时，有

$a^{k 1 + b 1} + b \equiv 0 (m o d C)$ ————式1

当n=2时，有

$a^{k 1 + b 1} a^{k 1} + b b^{k 2} \equiv 0 (m o d C)$ ————式2

又因为 $a^{k 1 + b 1} a^{k 1} + b a^{k 1} \equiv 0 (m o d C)$

所以有 $a^{k 1} \equiv b^{k 2} （ m o d C)$

显然，当n等于1，2时都满足等式的话，后面也是一定会满足的（归纳法）。

所以我们只要判断前两种情况就好了。具体来说，枚举a的所有可能值（1~C-1），然后根据式1算出b，再去判断a，b是否满足式2。由于是从小到大枚举a，因此一定是满足字典序的

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
typedef long long ll;
ll C, k1, k2, b1;

ll qpow(ll base, ll p) {
    if (p <= 0) return 1;
    ll res = qpow(base, p >> 1);
    res = res * 1ll * res % C;
    if (p & 1) res = res * 1ll * base % C;
    return res;
}

int main() {
    int kase = 0;
    while (cin >> C >> k1 >> b1 >> k2) {
        printf("Case #%d:\n", ++kase);
        int ans = 0;
        for (ll a = 1; a < C; a++) {
            ll b = C - qpow(a, k1 + b1);
            if ((qpow(a, (k1 << 1) + b1) + qpow(b, k2 + 1)) % C == 0) {
                printf("%lld %lld\n", a, b);
                ans++;
            }
        }
        if (ans == 0) printf("-1\n");
    }
}