暑期训练1：Codeforces Round #729 (Div. 2)B. Plus and Multiply

B. Plus and Multiply
time limit per test3 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
There is an infinite set generated as follows:

该集合包含数字1。
如果x属于此集合，则x乘以a和x加b也属于此集合。
例如，在a=3和b=6的情况下，该集合的前五个最小元素为：

第一行：
由于这是一个由特定规则生成的数集，
我们可以通过以下方式描述其生成规则：
当a \in S, 则a \cdot c \in S；
当b \in S, 则b + d \in S。
特别地，
给定正整数a,b,n, 我们需要确定n是否在上述所描述的数集中。

由多个测试案例组成。第一行包含一个整数t（1≤t≤105），表示测试案例的数量。这些测试案例的描述将随后给出。

Only one line exists for each test case to describe its details. The integers n, a, and b are specified within the same line and are separated by a single space between them. These values must satisfy the condition 1≤n,a,b≤109.

For each test case, you can print "Yes" if n is in this set and "No" otherwise. You are allowed to print each letter in any case.

For each test case, you can print "Yes" if n is in this set and "No" otherwise. You are allowed to print each letter in any case.

Example
inputCopy
5
24 3 5
10 3 6
2345 1 4
19260817 394 485
19260817 233 264
outputCopy
Yes
No
Yes
No
Yes
Note
In the first test case, 24 is generated as follows:

1 belongs to the given set. Therefore, both numbers following it—specifically, 3 and 6—are also included within the same collection.
Similarly, since 3 has been added to the group, the subsequent numbers 9 and 8 must also be part of it.
Following that logic, adding 8 into the mix necessitates the inclusion of 24 as well as 13. To conclude, we can observe that all these numbers share a common connection through their membership within the original collection.

In the second test case, the five smallest elements of the set are outlined in statements. Observations reveal that 10 is not included.

在本题中，默认情况下数字1被视为本问题的基础元素，在涉及a的乘法运算以及与b相关的加法运算中都扮演着不可或缺的角色。我们需要特别关注新的数字组中的求解过程，在这些计算过程中这个新的数字同样构成了新的基底并参与到后续更为复杂的计算当中。首先我们可以考虑采用循环的方法来解决这个问题其中当a等于1时是一种特殊情况因为无论n是多少都无法达到目标值这种情况下我们需要单独进行讨论在这种特殊情况下我们发现当b不等于1时如果n减去原有数据后再对b进行求余运算结果必然为零这表明我们应当针对a和b同时等于1的情况进行深入分析由于当a等于1时n对b取模的结果并不一定满足题目的条件而且此时还存在b等于1的情况因此我们需要分别讨论这两种情况为了简化讨论我们可以将余数设定为1模b的方式这样能够有效避免上述特殊情况的发生在后续代码编写过程中第二种方法虽然尝试将余数设置为1但忽略了这一特殊情况导致最终结果不够准确

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		long long a,b,n;
    		bool flag=false;
    		cin>>n>>a>>b;
    		if(a==1)
    		{
    			if(n%b==1%b)
    			  cout<<"YES"<<endl;
    			else
    			  cout<<"NO"<<endl;
    		}
    		else
    		{
    			for(long long i=1;i<=n;i*=a)
    			{
    				if((n-i)%b==0)
    				  flag=true;
    			}
    			if(flag)
    			  cout<<"YES"<<endl;
    			else
    			  cout<<"NO"<<endl;
    		}
    	}
     } 
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    代码解释

错误代码：

    #include<bits/stdc++.h>
    using namespace std;
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		long long a,b,n;
    		bool flag=false;
    		cin>>n>>a>>b;
    		if(a==1)
    		{
    			if(n%b==1)
    			  cout<<"YES"<<endl;
    			else
    			  cout<<"NO"<<endl;
    		}
    		else
    		{
    			for(long long i=1;i<=n;i*=a)
    			{
    				if((n-i)%b==0)
    				  flag=true;
    			}
    			if(flag)
    			  cout<<"YES"<<endl;
    			else
    			  cout<<"NO"<<endl;
    		}
    	}
     } 
    
    
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
    
    代码解释