专栏文章

题解：P14168 [Algo Beat Contest 002.5 C] 数数题 (count)

AA7F3jK9pR0xf_
P14168题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minolb6p
此快照首次捕获于
2025/12/02 05:48
3 个月前
此快照最后确认于
2025/12/02 05:48
3 个月前
查看原文
水题。
注意到 xa mod b∈[0,b)x^a\bmod b\in [0,b)，所以我们可以去枚举 xa mod bx^a\bmod b 的值。然后去一步步反着推回去。
首先观察到 f(x) mod 10≠0f(x)\bmod 10\neq 0，所以枚举的时候要把 10∣i10|i 的 ii 给删掉。
然后把第一层 ff 拆了，可以得到 f(x)=f(i)×10j−cf(x)=f(i)\times 10^j-c，为什么要乘 10j10^j，是因为计算 ff 的时候会把前导 00 删掉，而实际的值可能后面有很多 00。
然后判断 10∣f(x)10|f(x)，如果是就 pass 掉。
接着把第二层 ff 拆了，可以得到 x=f(f(x))×10kx=f(f(x))\times 10^k，后面乘 10k10^k 同理。
最后去验证 x∈[l,r]x\in [l,r] 且 xa mod b=ix^a\bmod b=i 即可。注意要特判拆完 ff 后可能会出现负数或者超过 101810^{18}。
时间复杂度 O(Tblog⁡a)O(Tb\log a) 再乘上枚举 j,kj,k 的 100100 的常数，基本不需要卡什么常。
CPP
#include <bits/stdc++.h>
using namespace std;
#define il inline
typedef long long ll;
const ll inf = 1e18;
int a, b, c;
il ll ppow(ll x, ll y)
{
	ll ans = 1;
	for(;y > 0;x = x * x % b, y >>= 1)
		if(y & 1) ans = ans * x % b;
	return ans;
}
il ll calc(ll x)
{
	ll ans = 0;
	while(x)
	{
		ans = ans * 10 + x % 10;
		x /= 10;
	}
	return ans;
}
ll p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000ll};
unordered_set<ll> ss;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t--)
	{
		ll l, r;
		cin >> l >> r >> a >> b >> c;
		ss.clear();
		for(int i = 0;i < b;++i)
		{
			if(i % 10 == 0) continue;
			ll fxx = calc(i);
			for(int j = 0;j <= 10;++j)
			{
				if(fxx >= (inf + c) / p10[j]) break;
				ll fx = fxx * p10[j] - c;
				if(fx < 0 || fx % 10 == 0) continue;
				ll x = calc(fx);
				if(x < 0 || x > r) continue;
				for(int k = 0;k <= 10;++k)
				{
					if(x >= inf / p10[k]) break;
					ll xx = x * p10[k];
					if(l <= xx && xx <= r && ppow(xx % b, a) == i) ss.insert(xx);
				}
			}
		}
		cout << ss.size() << "\n";
 	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...