[CCPC2024 重庆站] 有限小数 题解

· · 题解

回顾一下有限小数的定义：转换成分数并约分之后，分母必然为 2^x5^y(x,y\in\N) 的形式。

设 r 是 b 最大的不能被 2 或 5 整除的因数，那么存在 x,y\in\N 使得 d=2^x5^yr。

::::info[证明]

若存在质因数内不含 2,5 的 r'(r'\in\N^+\land r'>1) 满足：

::::

求出 r 后暴力枚举 x,y：设 V=10^9，由于 d\le V，所以这样的 d 的种类数是 O(\log^2 V) 的。

枚举 d 之后考虑求出最小的 c。考虑这个 c 要满足什么条件：\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}，分母 bd 最大的不能被 2 或 5 整除的因数为 r^2，所以只要满足 r^2\mid ad+bc。令 p=\frac{d}{r}，q=\frac{b}{r}，即 r\mid ap+qc\Leftrightarrow c\equiv-\frac{ap}{q}\pmod r。

问题转换为求 q^{-1}\bmod r。这个东西可以在循环外面用 exgcd 算，循环里面直接套上面的公式 O(1) 计算 c，对于全部的 c 取个最小值即为答案。总的时间复杂度 O(\log^2 V)，可以轻松通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int V=1e9;
pair<int,int> exgcd(int a,int b){
  if(!b)return make_pair(1,0);
  auto [x,y]=exgcd(b,a%b);
  return make_pair(y,x-a/b*y);
} // 扩展欧几里得算法
inline int inv(int x,int m){
  return (exgcd(x,m).first%m+m)%m;
} // 求乘法逆元
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int t; cin>>t;
  while(t--){
    int a,b,r; cin>>a>>b,r=b;
    while(!(r&1))r>>=1;
    while(!(r%5))r/=5;
    int q=(r-inv(b/r%r,r))%r;
    // 在外面提前计算出 b/r 的乘法逆元
    // 这里取了个相反数，这样里面就可以不用考虑那个负号
    // 也就是说这里的 q 相当于文章中的 q 的乘法逆元的相反数
    pair<int,int> rs(V,0);
    for(int d2=1;1ll*d2*r<=V;d2<<=1)
      for(int d5=1;1ll*d2*d5*r<=V;d5*=5){
        int p=d2*d5,d=p*r,c=1ll*q*a%r*p%r;
        rs=min(rs,make_pair(c,d));
      } // 暴力枚举 d，套公式算 c
    cout<<rs.first<<' '<<rs.second<<'\n';
  }
  return 0;
}