Educational Codeforces Round 66 (Rated for Div. 2) A

A. From Hero to Zero
제목 링크: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;
}


좋은 웹페이지 즐겨찾기