[AtCoder] [經典競程 90 題] 025 - Digit Product Equation(★7)

題目連結:https://atcoder.jp/contests/typical90/tasks/typical90_y
題目大意:
定義$f(x)$代表把$x$用十進位表示後每個位數的積。
接著給定$N$, $B$,問有多少個$1$到$N$的數$m$滿足$m-f(m)=B$。
因為其實總共只有12位數而已,所以就真的爆搜所有$f(m)$的值,接著移項就可以拿到$m=B+f(m)$,也就可以真的驗$f(m)$是不是對的,然後統計起來就好了。
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;

void dfs(int x, int d, vector<lld> &r, lld o) {
	r.push_back(o);
	if (d == 11) return;
	for (int i = x; i <= 9; ++i)
		dfs(i, d + 1, r, o * i);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	vector<lld> f{0};
	dfs(2, 0, f, 1);
	lld n, b; cin >> n >> b;
	unordered_set<lld> s;
	for (lld x: f) {
		lld o = x + b;
		if (o > n) continue;
		lld t = 1;
		for (; o; o /= 10) t *= o % 10;
		if (t == x) s.insert(x + b);
	}
	cout << s.size() << '\n';
	return 0;
} 

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology