快速幂题解

ac.nowcoder

题目

• 题目描述:立华奏在学习初中数学的时候遇到了这样一道大水题： “设箱子内有 n 个球，其中给 m 个球打上标记，设一次摸球摸到每一个球的概率均等，求一次摸球摸到打标记的球的概率” “emmm…语言入门题” 但是她改了一下询问方式：设最终的答案为 p ,请输出 p 小数点后 K1 到 K2 位的所有数字（若不足则用 0 补齐）
• 输入描述:第一行一个整数 T,表示有 T 组数据。接下来每行包含四个整数 m,n,K1,K2，意义如「题目描述」所示。
  • 1≤m≤n≤10的9次方,1≤K1≤K2≤10的9次方、0≤K2−K1≤10的5次方，T≤20。
• 输出描述:输出 T 行，每行输出 K2−K1+1个数，表示答案。注意同行的数字中间不需要用空格隔开。

解答

• 不用从头开始模拟，只需要从 K1 位开始模拟就可以了。 直接通过快速幂+取模算出第 K1位的数字。然后我们发现 K2−K1≤10的5次方，所以暴力枚举除法过程就可以。 时间复杂度 O(n)

  #include <algorithm>
  #include <iostream>
  #include <cstring>
  #include <climits>
  #include <cstdio>
  #include <vector>
  #include <cmath>
  #include <queue>
  #include <stack>
  #include <map>
  #include <set>
   
  #define Re register
  #define LL long long
  #define U unsigned
  #define FOR(i,a,b) for(Re int i = a;i <= b;++i)
  #define ROF(i,a,b) for(Re int i = a;i >= b;--i)
  #define CLR(i,a) memset(i,a,sizeof(i))
  #define BR printf("--------------------\n")
  #define DEBUG(x) std::cerr << #x << '=' << x << std::endl
   
  inline LL qpow(LL a,LL b,LL p){
      LL res = 1;
      for(;b;b>>=1,a=a*a%p)
          if(b&1) res = res * a % p;
      return res;
  }
   
  int main(){
      int T;
      scanf("%d", &T);
      while(T--){
          LL a,b,k1,k2;
          std::cin >> a >> b >> k1 >> k2;
          LL ans = ((a % b) % b * qpow(10, k1 - 1, b)) % b;
          for(LL i = k1;i <= k2;i++,ans = ans % b) {
              ans *= 10;
              std::cout << ans / b;
          }
          std::cout << std::endl;
      }
      return 0;
  }