本文主要是介绍Plus and Multiply（1500），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Plus and Multiply
题面翻译
有一个无穷大的正整数集合 S S S，该集合按下面所述方法生成：
-
数字 1 1 1 在集合 S S S 中。
-
若数字 x x x 在该集合中，那么数 x × a x \times a x×a 和数 x + b x+b x+b 均在集合 S S S 中。（其中 a a a 与 b b b 为给定常数）
现在给出数 n , a , b n,a,b n,a,b，请判断 n n n 是否在集合 S S S 中（此处给出的 a a a 与 b b b 就是上述集合生成方法中的 a a a 和 b b b），若在请输出 Yes，否则输出 No。多组数据。
令数据组数为 t t t，那么有 1 ≤ t ≤ 1 0 5 1 \leq t \leq 10^5 1≤t≤105， 1 ≤ n , a , b ≤ 1 0 9 1 \leq n,a,b \leq 10^9 1≤n,a,b≤109。
题目描述
There is an infinite set generated as follows:
- $ 1 $ is in this set.
- If $ x $ is in this set, $ x \cdot a $ and $ x+b $ both are in this set.
For example, when $ a=3 $ and $ b=6 $ , the five smallest elements of the set are:
- $ 1 $ ,
- $ 3 $ ( $ 1 $ is in this set, so $ 1\cdot a=3 $ is in this set),
- $ 7 $ ( $ 1 $ is in this set, so $ 1+b=7 $ is in this set),
- $ 9 $ ( $ 3 $ is in this set, so $ 3\cdot a=9 $ is in this set),
- $ 13 $ ( $ 7 $ is in this set, so $ 7+b=13 $ is in this set).
Given positive integers $ a $ , $ b $ , $ n $ , determine if $ n $ is in this set.
输入格式
The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1\leq t\leq 10^5 $ ) — the number of test cases. The description of the test cases follows.
The only line describing each test case contains three integers $ n $ , $ a $ , $ b $ ( $ 1\leq n,a,b\leq 10^9 $ ) separated by a single space.
输出格式
For each test case, print “Yes” if $ n $ is in this set, and “No” otherwise. You can print each letter in any case.
样例 #1
样例输入 #1
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
样例输出 #1
Yes
No
Yes
No
Yes
提示
In the first test case, $ 24 $ is generated as follows:
- $ 1 $ is in this set, so $ 3 $ and $ 6 $ are in this set;
- $ 3 $ is in this set, so $ 9 $ and $ 8 $ are in this set;
- $ 8 $ is in this set, so $ 24 $ and $ 13 $ are in this set.
Thus we can see $ 24 $ is in this set.
The five smallest elements of the set in the second test case is described in statements. We can see that $ 10 $ isn’t among them.
思路：因为只有乘法和加法假设数为x，则我们先乘以a然后在加上b，与我们先加上b在乘以a其实是等价的，因为变换次数是无限的，因此我们可以想到n = a的x次方 + b的y次方，因为指数型函数指数爆炸式增长，因此我们来枚举x，枚举过程中我们只需要判断n - a的x次方对b取模是不是0即可
AC代码：
#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int>PII;
typedef pair<int, double>PDD;
const int N=2e5 +10;
const int MOD = 1e9 + 7;
const int INF=0X3F3F33F;
const int dx[]={-1,0,1,0,-1,-1,+1,+1};
const int dy[]={0,1,0,-1,-1,+1,-1,+1}; //马
const int dxx[]={-1,2,1,1,-1,2,-2,-2};
const int dyy[]={2,1,-2,2,-2,-1,-1,1};
const int M = 1e7 + 10;int t;
int main()
{cin >> t;while(t --){ll n, a, b;cin >> n >> a >> b;if(a == 1){if((n - 1) % b == 0) puts("Yes");else puts("No");}else {int f = 0;for(ll i = 1; i <= n; i *= a){if((n - i) % b == 0){f = 1;break;}}if(f) puts("Yes");else puts("No");}}return 0;
}
这篇关于Plus and Multiply（1500）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
