Codeforces1542B Plus and Multiply (思维)
题目链接:
大致题意
有一个无穷集合, 初始集合内有整数1, 现给定你整数a和b. 集合内部元素有如下定义: 若x存在于集合中, 则x * a存在于集合中, x + b也存在于集合当中.
请你判断整数n是否存在于集合中.
解题思路
为简化说明, 我们定义: 操作①: x * a 操作②: x + b
我们不妨先假设n存在于集合中, 则n一定可以由1经过若干次操作①和②的排列组合得到. 我们不妨看看操作①和②有什么关系.
假设现有数字x, 我们如果执行②①, 则 x’ = (x + b) * a = ax + ab. 如果我们再给x’执行操作① x’’ = (ax + ab) * a = a2x + a2b 如果我们给x’执行操作② x’’’ = (ax + ab) + b = ax + (a + 1)b 如果我们给x’’执行操作① x4 = [ax + (a + 1)b] * a = a2x + (a2 + a)b.
通过上述举例, 可以得到发现: 我们通过x进行一系列操作得到的数字都可以写作: x’ = ac1 * x + c2 * b (其中c1和c2为系数.)
我们不妨这样想, 给一个数字x加了b之后(操作②), 再乘a(操作①), 和这个数字先乘a(操作①), 再加上a次的b(a次操作②) 其实是一样的. 因此我们可以混淆这两种操作, 我们可以得到的数字都可以由上述的通式来表示. 反之, 若不能得到, 则不能由上述通式来表示.
因此我们只需要判断n是否符合上述通式即可.
我们不失一般性, 不妨取x = 1, 看看能否找到某个x’ = ac1 + c2 * b, 使得 x == n 成立.
由于上述的通式是一个不定解方程, 我们会得到若干组 c1和c2 的解, 但我们只需要找到任一组存在的解即可. 比较常用的方式是, 我们可以去枚举其中的某个变量.
对于本题, 我们应当枚举c1, 判断是否存在某个c2使得等式成立即可.
假设a != 1, 则a ≥ 2. n最大取值为1E9 我们的操作①是, 每次给x乘a, 因此我们最多枚举logn次c1的取值. 就可以判断是否存在合法解c2. 如果a == 1的话, 上述通式可以化简为 x = 1 + c2 * b , 这是一个定解方程, 我们可以直接计算出c2. 倘若我们去枚举c2的取值, 我们最坏将枚举O(n)次得到答案, 这显然是不成立的.
AC代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
int main()
{
int t; cin >> t;
while (t--) {
int n, a, b; scanf("%d %d %d", &n, &a, &b);
if (a == 1) {
//特判
puts((n - 1) % b ? "No" : "Yes");
continue;
}
ll now = 1; bool flag = 0;
while (now <= n) {
if ((n - now) % b == 0) {
flag = 1; break;
}
now *= a;
}
puts(flag ? "Yes" : "No");
}
return 0;
}
