月夜飒飒动干戈 --- DYOI系列题解

MuLinnnnn · 2025-08-10 08:03:59 · 算法·理论

简略题意：求出所有的 i 使 k^i=z，p\le i \le p + 9 。

由于 i 的范围极小，只需要枚举 10 个数字，所以暴力检查每一个 i 是否符合要求；计算部分使用带模的快速幂并只取出个位数即可。

快速幂如下：

inline ll qpow(ll a, ll b, ll mod) {
    ll ret = 1;
    while(b > 0) {
        if(b & 1) {
            ret *= a, ret %= mod;
        }
        a *= a, a %= mod;
        b >>= 1;
    }
    return ret;
}

枚举部分如下

for(ll i = p; i <= p + 9; ++i) {
    if(qpow(k, i, 10) == x) {
        ans[tot++] = i;
    }
}

最后的统计与存储过于简单不放代码了。

总代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans[13];

inline ll qpow(ll a, ll b, ll mod) {
    ll ret = 1;
    while(b > 0) {
        if(b & 1) {
            ret *= a, ret %= mod;
        }
        a *= a, a %= mod;
        b >>= 1;
    }
    return ret;
}

int main() {
    ll T;
    cin >> T;
    while(T--) {
        ll k, p, x;
        cin >> k >> p >> x;
        ll tot = 0;
        k %= 10;
        for(ll i = p; i <= p + 9; ++i) {
            if(qpow(k, i, 10) == x) {
                ans[tot++] = i;
            }
        }
        if(tot == 0) {
            cout << "No Ans" << endl;
        } else {
            cout << tot << endl;
            for(ll i = 0; i < tot; ++i) {
                cout << ans[i] << ' ';
            }
            cout << endl;
        }
    }
    return 0;
}