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

简略题意：求出所有的

i

使

k^i=z，p\le i \le p + 9

。

由于

i

的范围极小，只需要枚举

10

个数字，所以暴力检查每一个

i

是否符合要求；计算部分使用带模的快速幂并只取出个位数即可。

快速幂如下：

CPP

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;
}

枚举部分如下

CPP

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

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

总代码：

CPP

#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;
}

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

文章操作

相关推荐

评论

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