Problem 5. 无理数位数查询【算法赛】

思路：

m进制n为数有(m-1)*m^(n-1)个 可以先确定答案所在区间

#include <bits/stdc++.h>
using namespace std;
int main()
{
  // 请在此输入您的代码
  ios::sync_with_stdio(false);
  int t;
  cin>>t;
  while(t--){
      long long n,m;
      cin>>n>>m;
      long long cnt=m-1,base=1;
      int curr =  1;
      while(n>curr*cnt){
          n -= curr*cnt;
          curr++;
            base*=m;
            cnt*=m;
      }
        base+=(n-1)/curr;
        n %= curr;
        if(n==0) n = curr;
        int ans = base%m;
        for(int i=0;i<curr+1-n;i++){
            ans = base%m;
            base /= m;
        }
        cout <<ans<<endl;
  }
  return 0;
}