Educational Codeforces Round 66 (Rated for Div. 2) A
4468 단어 codeforces 작은 일상
제목 링크:http://codeforces.com/contest/1175/problem/A
제목.
You are given an integer n and an integer k In one step you can do one of the following moves: decrease n by 1; divide n by k if n is divisible by k. For example, if n=27 and k=3 you can do the following steps: 27→26→25→24→8→7→6→2→1→0. You are asked to calculate the minimum number of steps to reach 0 from n.
Input
The first line contains one integer t (1≤t≤100) — the number of queries. The only line of each query contains two integers n and k (1≤n≤1018, 2≤k≤1018).
Output
For each query print the minimum number of steps to reach 0 from n in single line
제목
n,k 두 개 를 드 리 겠 습 니 다.n 을 매번 다음 과 같은 두 단계 중 하 나 를 거 쳐 0 을 받 아야 합 니 다.출력 변환 횟수:n=n-1 또는 n=n/k(전제 n 은 k 를 제거 할 수 있 습 니 다).
사고의 방향
범위 가 너무 넓 고 폭력 은 절대 TLE 입 니 다.시 도 는 생명 을 낭비 하 는 것 입 니 다!교묘 한 방법:n%k!=0 시 변 경 된 걸음 수 는 n%k 의 값 입 니 다.이때 현재 n=(n-이 걸음 수 를 뺀)n%k==0 시 변 경 된 걸음 수 는 1 입 니 다.이때 현재 n=n/k,n 은 0 으로 끝나 고 걸음 수 를 누적 출력 하면 됩 니 다.
#include
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int main()
{
int T;
cin>>T;
while(T--) {
ll n, k;
cin >> n >> k;
ll result = 0;
while (n != 0) {
ll book = n % k;
if (book != 0) {
result += book;
n = n - book;
} else {
result += 1;
n = n / k;
}
}
cout << result << endl;
}
return 0;
}