#每日一题：小数第n位（数论/模拟）

喜欢ヅ旅行 2023-07-10 12:54 7阅读 0赞

# 试题 历届试题 小数第n位 #

资源限制  
时间限制：1.0s 内存限制：256.0MB

--------------------

**Daily English**

> 你做过的事，就永远不会忘，即便你会想不起来。  
> Once you do something,you never forget.Even if you can’t remember.

## 问题描述 ##

我们知道，整数做除法时，有时得到有限小数，有时得到无限循环小数。  
　　如果我们把有限小数的末尾加上无限多个0，它们就有了统一的形式。

本题的任务是：在上面的约定下，求整数除法小数点后的第n位开始的3位数。  
输入格式  
　　一行三个整数：a b n，用空格分开。a是被除数，b是除数，n是所求的小数后位置（0<a,b,n<1000000000）  
输出格式  
　　一行3位数字，表示：a除以b，小数后第n位开始的3位数字。

## 样例输入 ##

1 8 1

## 样例输出 ##

125

## 样例输入 ##

1 8 3

## 样例输出 ##

500

## 样例输入 ##

282866 999000 6

## 样例输出 ##

914

## 思路： ##

*  way1：  
    明确结果只取3位，从n开始取，包括第n位，还要取两位，a,b,n可达1e9。  
    假设没有精度问题，我们算出来的结果，要取小数点后面的几位，  
    一般我们会先把小数扩大（10^x）倍，将结果转化为整数，然后取余。  
    所以问题转化一下：  
    **ans = a / b \* 10^(n+2) % 1000;**  
    求解ans。  
    由于b可能很大，所以a/b就会因精度问题而算不到正确结果。  
    上面的式子可以看成：  
    **a/b mod m**  
    这就很容易想到：  
    在**模m意义下**，a除以b 模m 等同于 a乘以 **b的逆元（inv(b)）** 模 m  
    即： **a/b mod m = a \* inv(b) mod m**  
    所以：  
    **ans = a \* inv(b) \* 10^(n+2) % 1000;**  
    此时模m=1000，不是质数，所以不能通过**费马小定理来求解逆元**；  
    不能保证b与m互质（gcd（b,m）= 1），所以也不能通过**扩展欧几里得来求解逆元**。

当逆元无法来求解的时候，需要考虑一个一般公式(转化成不需要求解逆元)：**a / b % m = a % (b\*m) / b**  
证明见：[证明详情][Link 1]

所以根据公式a / b % m = a % (b\*m) / b 问题转化：

**ans = a \* 10^(n+2) % (b\*1000) / b**

注意输出，结果没有3位要补0。

way2：  
第二种方法就是模拟一下手算，如果出现无限循环的情况是怎么样的。  
比如：1 / 3：  
小数第一位： 1 \* 10 / 3  
第二位：10%3 = 1，1 \* 10 / 3。。。  
发现**只要被除数再次出现**就会陷入循环（出现循环节）。  
所以我们就可以**只 算到一个循环 并记录下来**，  
后面的**根据记录直接推出**（详见代码）。

## 代码： ##

### way1 数论 ###

#include <iostream>
    #include <cstdio>
    using namespace std;
    typedef long long LL;
    LL quickPow(LL a,LL b,LL mod)
    {
        
        LL res = 1;
        a %= mod;
        while(b)
        {
        
            if(b&1) res = res * a % mod;
            a  = a * a % mod;
            b >>= 1;
        }
        return res%mod;
    }
    int main()
    {
        
        int a,b,n;
        scanf("%d%d%d",&a,&b,&n);
        LL mod = b * 1000;
        LL t = quickPow(10,n+2,mod);
        int ans = a % mod * t % mod;
        printf("%03d\n",ans/b);
        return 0;
    }

### way2模拟 ###

/*
    s:记录一个循环的开始处
    e:记录一个循环的截至处
    mp1[i]：记录被除数i是否出现
    mp2[i]：记录第i个小数是多少
    mp3[i]:记录被除数为i时 所对应的小数 在的位置
    */
    #include <iostream>
    #include <map>
    using namespace std;
    map<int,int>mp1;
    map<int,int>mp2;
    map<int,int>mp3;
    int s,e;
    void calc(int a,int b)
    {
        
        a %= b;
        //没有循环，后面通过补0，可以统一当作有循环处理
        while(1)
        {
        
            a *= 10;
            if(!mp1[a])
            {
        
                mp1[a]++;
                mp2[++e] = a / b;
                mp3[a] = e;
            }
            else
            {
        
                //所以是再次出现被除数时才跳出循环
                s = mp3[a];
                break;
            }
            a %= b;
        }
    }
    int getAns(int n)
    {
        
        return n <= e ? mp2[n] : mp2[(n-s)%(e-s+1)+s];
    }
    int main()
    {
        
        int a,b,n;
        cin>>a>>b>>n;
        s = e = 0;
        calc(a,b);
        for(int i = n; i < n+3; i++)
        {
        
            cout<<getAns(i);
        }
        cout<<endl;
        return 0;
    }

[Link 1]: https://blog.csdn.net/qq_41289920/article/details/81270653?depth_1-utm_source=distribute.pc_relevant.none-task&utm_source=distribute.pc_relevant.none-task