Plus and Multiply（1500）

2024-08-29 10:52

文章标签 plus 1500 multiply

本文主要是介绍Plus and Multiply（1500），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Plus and Multiply

题面翻译

有一个无穷大的正整数集合 $S$ ，该集合按下面所述方法生成：

数字 $1$ 在集合 $S$ 中。
若数字 $x$ 在该集合中，那么数 $\times a$ 和数 $x + b$ 均在集合 $S$ 中。（其中 $a$ 与 $b$ 为给定常数）

现在给出数 $n, a, b$ ，请判断 $n$ 是否在集合 $S$ 中（此处给出的 $a$ 与 $b$ 就是上述集合生成方法中的 $a$ 和 $b$ ），若在请输出 Yes，否则输出 No。多组数据。

令数据组数为 $t$ ，那么有 $\leq t \leq 10^5$ ， $\leq n,a,b \leq 10^9$ 。

题目描述

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;
}