藍橋杯 試題 曆屆試題 小數第n位

題目連結：http://lx.lanqiao.cn/problem.page?gpid=T456

題意：

問題描述

　　我們知道，整數做除法時，有時得到有限小數，有時得到無限循環小數。

　　如果我們把有限小數的末尾加上無限多個0，它們就有了統一的形式。

　　本題的任務是：在上面的約定下，求整數除法小數點後的第n位開始的3位數。

輸入格式

　　一行三個整數：a b n，用空格分開。a是被除數，b是除數，n是所求的小數後位置（0<a,b,n<1000000000）

輸出格式

　　一行3位數字，表示：a除以b，小數後第n位開始的3位數字。

思路：其實就是求(a/b)*10(n+2)%1000。因為1000不是素數，是以無法應用逆元，但是對于這種情況， a b \frac ab ba​%m可以化成 a % ( b m ) b \frac {a\%(bm)}b ba%(bm)​。

#include<bits/stdc++.h>
using namespace std;
long long qsm(long long a,long long b,long long mod)
{
    long long base=a,sum=1;
    while(b)
    {
        if(b&1)
        {
            sum=sum*base%mod;
        }
        b>>=1;
        base=base*base%mod;
    }
    return sum;
}
int main()
{
    long long a,b,n;
    cin>>a>>b>>n;
    long long mod=b*1000;
    long long ans=((a%mod)*qsm(10,n+2,mod))%mod;
    printf("%03d",ans/b);
    return 0;
}