【题解】无聊的立华奏

题目描述

立华奏在学习初中数学的时候遇到了这样一道大水题&＃xff1a;

“设箱子内有 n 个球&＃xff0c;其中给 m 个球打上标记&＃xff0c;设一次摸球摸到每一个球的概率均等&＃xff0c;求一次摸球摸到打标记的球的概率。”

“emmm…语言入门题。”

但是她改了一下询问方式&＃xff1a;设最终的答案为 p&＃xff0c;请输出 p 小数点后 K1 到 K2 位的所有数字&＃xff08;若不足则用 0 补齐&＃xff09;。

输入格式

第一行一个整数 T&＃xff0c;表示有 T 组数据。

接下来每行包含四个整数 m&＃xff0c;n&＃xff0c;K1&＃xff0c;K2&＃xff0c;意义如「题目描述」所示。

输出格式

输出 T 行&＃xff0c;每行输出 K2 - K1 &＃43; 1 个数&＃xff0c;表示答案。

注意同行的数字中间不需要用空格隔开。

输入样例

5
2 3 2 3
1 7 1 7
2 5 1 3
12345 54321 3 10
12345 54321 100000 100010

输出样例

66
1428571
400
72601756
78428232175

说明

对于 100% 的数据&＃xff0c;1≤m≤n≤1091 ≤ m ≤ n ≤ 10^91≤m≤n≤109&＃xff0c;1≤K1≤K2≤1091 ≤ K1 ≤ K2 ≤ 10^91≤K1≤K2≤109&＃xff0c;0≤K2−K1≤1050 ≤ K2 - K1 ≤ 10^50≤K2−K1≤105&＃xff0c;$T\le 20$。

对于求概率&＃xff0c;直接用 $m/n$ 即可。

若 $m/n$ 结果为有限小数&＃xff0c;设小数位数为 $x$&＃xff0c;m/n∗10xm/n*10^xm/n∗10x 即为 $m/n$ 去掉小数点后的数字&＃xff0c;(m∗10x/n)mod10(m*10^x/n) mod 10(m∗10x/n)mod10 为去掉小数点后的数字的最后一位&＃xff0c;即原数的小数点后第 $x$ 位。

进一步得出&＃xff0c;求小数点后第 $i$ 位数字&＃xff0c;即为 int(m∗10i/n)mod10int(m*10^i/n)mod 10int(m∗10i/n)mod10。

其中 10i10^i10i 可直接用快速幂求出。

但是对于 int(m∗10i/n)mod10int(m*10^i/n)mod 10int(m∗10i/n)mod10 而言&＃xff0c;其中 m∗10im*10^im∗10i 容纳不了太多的位数&＃xff0c;怎么办呢&＃xff1f;

这时可以想到&＃xff1a;
$(a/n)mod10$
若 $a>10n$&＃xff0c;则&＃xff1a;

原式
$\&＃61;((a-10n\&＃43;10n)/n)mod10$
$\&＃61;((a-10n)/n\&＃43;10n/n)mod10$
$\&＃61;((a-10n)/n\&＃43;10)mod10$
$\&＃61;((a-10n)/n)mod10$
进一步&＃xff0c;可以想到 $a$ 和 $amod10$ 的结果是相同。

把此式代入 (m∗10i/n)mod10(m*10^i/n)mod 10(m∗10i/n)mod10&＃xff0c;有&＃xff1a;
(m∗10i/n)mod10(m*10^i/n)mod 10(m∗10i/n)mod10
&＃61;int(10i∗((m−10n&＃43;10n)/n))mod10&＃61;int(10^i*((m-10n&＃43;10n)/n))mod 10&＃61;int(10i∗((m−10n&＃43;10n)/n))mod10
&＃61;int(10i∗((m−10n)/n&＃43;10n/n))mod10&＃61;int(10^i*((m-10n)/n&＃43;10n/n))mod 10&＃61;int(10i∗((m−10n)/n&＃43;10n/n))mod10
&＃61;int(10i∗((m−10n)/n&＃43;10))mod10&＃61;int(10^i*((m-10n)/n&＃43;10))mod 10&＃61;int(10i∗((m−10n)/n&＃43;10))mod10
&＃61;int(10i∗(m−10n)/n&＃43;10i∗10)mod10&＃61;int(10^i*(m-10n)/n&＃43;10^i*10)mod 10&＃61;int(10i∗(m−10n)/n&＃43;10i∗10)mod10
&＃61;int(10i∗(m−10n)/n)mod10&＃61;int(10^i*(m-10n)/n)mod 10&＃61;int(10i∗(m−10n)/n)mod10
&＃61;int(10i∗(mmod10n)/n)mod10&＃61;int(10^i*(mmod10n)/n)mod 10&＃61;int(10i∗(mmod10n)/n)mod10
&＃61;int(((10i∗(mmod10n))mod10n)/n)mod10&＃61;int(((10^i*(mmod10n))mod10n)/n)mod 10&＃61;int(((10i∗(mmod10n))mod10n)/n)mod10

便变成了快速幂求 $mod10n$ 的余数了。

#include
#include
using namespace std;
long long t,n,m,k1,k2;
/*
m*10
if m>&＃61;n then m-n若循环节长度为 x
(m*10^x)/n为循环节数字的整数形式
求第小数点后 i 为即为 ((m*10^i)/n)%10对于 (a/b)%10
如果 a 大于 10b&＃xff0c;则有 (a/b)%10
&＃61;((a-10b&＃43;10b)/b)%10
&＃61;((a-10b)/b&＃43;10b/b)%10
&＃61;((a-10b)/b&＃43;10)%10
&＃61;((a-10b)/b)%10
因此对于 a 和 (a-10b) 而言&＃xff0c;结果相同 所以&＃xff1a;
((m*10^i)/n)%10
&＃61;(((m*10^i)%10n)/n)%10
*/
long long pow(long long i)
{long long ans&＃61;m%(10*n),a&＃61;10;while(i){if(i&1)ans&＃61;(ans*a)%(10*n);a&＃61;(a*a)%(10*n);i>>&＃61;1;}return ans;
}
int main()
{cin>>t;while(t--){cin>>m>>n>>k1>>k2;for(long long i&＃61;k1;i<&＃61;k2;i&＃43;&＃43;)cout<<(pow(i)/n)%10;cout<<&＃39;\n&＃39;;}return 0;
}