CF1542B Plus and Multiply – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
\(T = \{a^x +yb \text{ } \vert \text{ } x, y \in N\}\) 和 \(S\) 相等。
证明:
- \(S \subseteq T\):显然有 \(1 \in T\)。然后有 \((a^x+yb) \times a = a^{x+1} + (ay)b\),\((a^x + yb) + b = a^{x+1} + (y+1)b\)。
- \(T \subseteq S\):\(a^x + yb\) 可以由 \(1\) 乘 \(x\) 次 \(a\) 再加 \(y\) 次 \(b\) 得到。
因此 \(S = T\)。
那么问题可以转化为 \(n\) 是否可以表示为 \(a^x + yb\),其中 \(x, y \in N\)?
容易发现当 \(a \ne 1\) 时,\(x\) 的范围很小。枚举 \(x\) 即可。然后检验 \(y\) 是否为 \(n – a^x\) 的因数。
\(a = 1\) 时容易特判:只需要检验 \(n \bmod b = 1\) 或 \(b = 1\) 即可(注意 \(X \bmod 1 = 0\))。
单组数据 \(\mathcal{O}(\log n)\)。
/*
* @Author: crab-in-the-northeast
* @Date: 2022-10-14 01:41:35
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2022-10-14 01:52:57
*/
#include <bits/stdc++.h>
#define int long long
inline int read() {
int x = 0;
bool flag = true;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
flag = false;
ch = getchar();
}
while (isdigit(ch)) {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
if(flag)
return x;
return ~(x - 1);
}
signed main() {
int T = read();
while (T--) {
int n = read(), a = read(), b = read();
if (a == 1) {
if (b == 1 || n % b == 1)
puts("Yes");
else
puts("No");
continue;
}
bool fl = false;
for (int X = 1; X <= n; X *= a) {
if ((n - X) % b == 0) {
fl = true;
break;
}
}
puts(fl ? "Yes" : "No");
}
return 0;
}
原文地址:http://www.cnblogs.com/crab-in-the-northeast/p/cf1542b.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性