#729 (Div. 2) B - Plus and Multiply

문제 링크 => Problem - B - Codeforces

Problem - B - Codeforces

---

Problem tags : constructive algorithms, math, number theory 

 

문제의 조건을 보면 다음과 같다.

• 1 is in this set.
• If x is in this set, x⋅a and x+b both are in this set.

예를 들어서 a=3, b=5 라고 가정해보자.

 

이때 1은 기본적으로 set에 포함된다.

 

그리고 두번째 조건을 통해 1 * 3 = 3 , 1 + 5 = 6 으로 3, 6 값이 set에 포함된다.

 

3을 기준으로 보면? => 3 * 3 = 9, 3 + 5 = 8 으로 9, 8 값이 set에 포함된다.

 

6을 기준으로 보면? => 6 * 3 = 18, 6 + 5 = 11 으로 18, 11 값이 set에 포함된다.

 

이때 n 값이 a, b의 곱셈과 덧셈 operation 을 통하여 만들어지는지 확인해줘야 한다.

 

그러나 n, a, b 값이 최소 1 부터 최대 10^9 까지로 주어지므로 덧셈 operation 을 사용하는것은 최대한 비효율적인 것임을 나중에야 파악하게 되었다.

 

따라서 곱셈 operation 을 적용하고 그 후에 덧셈 operation 을 하도록 구현하는것이 맞는걸 알 수 있다.

 

그러나... a 값이 1인 경우? => 1에 1을 곱하면 계속 1이 되므로 결국 덧셈 operation 을 적용해야 한다.

 

따라서 두가지 Case 를 나눴다.

 

Case 1 : a 값이 1인 경우 => (n - 1) % b 값이 0 인 경우 즉, 1+b+b+...+b 값이 결국 n 이 되는지 파악만 하면 끝이다.

 

Case 2 : a 값이 2이상인 경우 => 다음과 같은 과정을 거쳐서 조건이 만족하는 경우를 찾도록 하였다.

   1) 1 + x = n => x 값이 b의 덧셈 operation 으로 만들어지는 경우 ( x % b == 0 )

   2) a + x = n => x 값이 b의 덧셈 operation 으로 만들어지는 경우 ( x % b == 0 )

   3) a^2 + x = n => x 값이 b의 덧셈 operation 으로 만들어지는 경우 ( x % b == 0 )

   ...

   c-1) a^c + x = n => x 값이 b의 덧셈 operation 으로 만들어지는 경우 ( x % b == 0 )

 

x 값이 양수일때까지 위 과정을 반복해주면서 x % b == 0 을 만족하도록 하는 c 값이 발견될 경우 set에 포함되는것임을 알 수 있다.

 

이때 시간 복잡도는 O(logN) 임을 알 수 있다.

---

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'

using namespace std;

void test() {
	long long n, a, b;
	cin >> n >> a >> b;
	if (a == 1) {
		if ((n - 1) % b == 0) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
	else {
		long long t = 1;
		while (1) {
			long long x = n - t;
			if (x < 0) break;
			if (x % b == 0) {
				cout << "Yes"<<endl;
				return;
			}
			t *= a;
		}
		cout << "No" << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		test();
	}


	return 0;
}