HDU5478-Can you find it

题目大意

有一个对于一个有序数对$(a,b)$和$k1,k2,b1$，要求满足等式 $a^{k1⋅n+b1}+ b^{k2⋅n−k2+1} \equiv 0 (mod C)(\forall n = 1, 2, 3, ...)$

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

分析

当n=1时，有

$a^{k1+b1}+b\equiv0(modC)$ ————式1

当n=2时，有

$a^{k1+b1}a^{k1}+bb^{k2}\equiv0(modC)$ ————式2

又因为 $a^{k1+b1}a^{k1}+ba^{k1}\equiv0(modC)$

所以有$a^{k1}\equiv b^{k2}（modC)$

显然，当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");
    }
}