codeforces 1542B. Plus and Multiply（1500）

题目链接：https://codeforces.ml/problemset/problem/1542/B

题目大意：有一个集合，集合里面的数满足

• 1
• 如果x在集合里面, x⋅a和x+b也在

   然后输入n.a.b，判断n在不在集合里面 

题解：数论题，经过推算发现集合里面的数满足n=a^k1+b*k2，接下来枚举k1（0<=k1）,去找对应k2

代码：

#include<iostream>
using namespace std;
typedef long long ll;

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		ll n, a, b;
		cin >> n >> a >> b;
		int flag = 1;
		ll cnt = 1;
		if (n != 1)
		{
			if (a != 1)//特判1，要不然会超时
			{
				while (cnt <= n)
				{
					if ((n - cnt) % b == 0)
					{
						flag = 0;
						break;
					}
					cnt = cnt * a;
				}
				if (flag == 0)cout << "Yes" << endl;
				else
				{
					cout << "No" << endl;
				}
			}
			else
			{
				if((n-1)%b==0)cout << "Yes" << endl;
				else
					cout << "No" << endl;

			}
		}
		else
		{
			cout << "Yes" << endl;
		}
	}
	return 0;
}