Plus and Multiply（1500）

Plus and Multiply

题面翻译

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

数字 1 在集合 S 中。

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

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

令数据组数为 t，那么有 1 \leq t \leq 10^5，1 \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;
    }