[原创]2017年第0届浙江工业大学之江学院程序设计竞赛决赛 K: qwb与小数 [快速幂]【思维】

2017-06-03 02:50:11 Tabris_ 阅读数：389

博客爬取于2020-06-14 22:40:12
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72849793

题目链接：http://115.231.222.240:8081/JudgeOnline/problem.php?cid=1005&pid=10
——————————————————————————————————————————
Problem K: qwb与小数
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 382 Solved: 71
[Submit][Status][Web Board]
Description
qwb遇到了一个问题：将分数a/b化为小数后，小数点后第n位的数字是多少？

做了那么多题，我已经不指望你能够帮上他了。。。

Input
多组测试数据，处理到文件结束。（测试数据<=100000组）

每组测试例包含三个整数a，b，n，相邻两个数之间用单个空格隔开，其中0 <= a <1e9，0 < b < 1e9，1 <= n < 1e9。

Output
对于每组数据，输出a/b的第n位数，占一行。
Sample Input
1 2 1
1 2 2
Sample Output
5
0
HINT
——————————————————————————————————————————

在dalao们的帮助下，会了

a10^(n-1)%b10/b;
a10^(n-1)%b前面留在其他位的都不影响结果
最后10/b也就是我们要的结果了

其实没后面一位就是a*10/b 做了n次而已

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# include<bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N = 8000000+7;
//const int MOD = 1e9+7;
const double Pi = acos(-1.0);

int read(){
    int x=0,f=1;char ch= getchar();
    while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
/******************************/

LL MOD,x,n;
LL qmod(LL a,LL b){
    LL res = 1ll;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1,a=a*a%MOD;
    }
    return res;
}
int main(){
    while(~scanf("%lld%lld%lld",&x,&MOD,&n)){
        printf("%lld\n",(x%MOD*qmod(10,n-1))%MOD*10/MOD);
    }
    return 0;
}