学习随笔——codeforces题目Plus and Multiply解答

摘要：构造算法与数论的结合，巧妙之处在于我们要自己模拟一遍计算过程然后从中找出特殊点。

题目原地址如下：https://codeforces.com/problemset/problem/1542/B

题目截图如下：

 关键词：构造算法，数论，*1500

简要翻译：一个无穷集合中的元素由如下规则生成：x=m*a或者x=m+b，其中a,b给定，m为集合元素。在生成初期，集合中包含1。现给定数k，要我们求出k是否在这个无穷集合内。

考察上述运算过程，我们可以知道，因为1的存在，上述生成过程一定存在一个分量为未乘b的量，只需按幂次依次遍历判断即可。

特别注意，当a=1时会出现死循环，需要特判。

代码如下：

 1 #include <iostream>
 2 #define ll long long
 3 using namespace std;
 4 ll a,b,n,l;
 5 void solve(ll a,ll b,ll n){
 6     if (a==1){//特判情况 
 7         if ((n-1)%b==0){
 8             cout<<"YES"<<endl;
 9             return ;
10         }
11         else{
12             cout<<"NO"<<endl;
13             return ;
14         }
15     }
16     if ((n-1)%b==0){
17         cout<<"YES"<<endl;
18         return ;
19     }
20     ll a1=a;
21     while (a1<=n){
22         if ((n-a1)%b==0){
23             cout<<"YES"<<endl;
24             return ;
25         }
26         a1*=a;
27     }
28     if (a1>n){
29         cout<<"NO"<<endl;
30         return ;
31     }
32 }
33 int main(){
34     cin>>l;
35     while(l--){
36         cin>>n>>a>>b;
37         solve(a,b,n);
38     }
39     return 0;
40 }