一个分数 可能为无限循环小数和有限不循环小数
定理: 有理数的简单运算不会出现无理数(无限不循环小数)
求第n位小数时按照除法过程模拟即可求得答案
1.余数乘十后除除数
2.余数模除数
goto 1;
直到求得答案
该算法时间复杂度O(n)
则需引入对于循环小数的特殊处理
则可用map容器记录<除数,位置>
易得除数重复出现时即为循环节的开闭两端, 后部可不必计算
由此取余即为最终答案
/*
Zeolim - An AC a day keeps the bug away
*/
//pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <sstream>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
int arr[MAXN] = {0};
map <int, int> rpos;
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
//freopen("D://test.in", "r", stdin);
//freopen("D://test.out", "w", stdout);
ll a, b, n, t = MAXN, rt = MAXN;
cin>>a>>b>>n;
a %= b;
for(int i = 0; i < n + 2; i++)
{
a *= 10;
if(rpos[a])
{
t = rpos[a];
rt = i;
break;
}
arr[i] = a / b;
rpos[a] = i;
a %= b;
}
if(n + 1 < rt)
cout<<arr[n - 1]<<arr[n]<<arr[n + 1]<<'
';
else
cout<<arr[ ((n - 1 - t) % (rt - t)) + t]<<arr[ ((n - t) % (rt - t)) + t]<<arr[( (n - t + 1) % (rt - t) ) + t]<<'
';
return 0;
}
方法2:
整数位模掉对小数位无影响
1 /10 = 0.1;
1 * 10 / 10 = 1;
则可快速进位逼近要求的小数位
/*
Zeolim - An AC a day keeps the bug away
*/
//pragma GCC optimize(2)
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <sstream>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//freopen("D://test.in", "r", stdin);
//freopen("D://test.out", "w", stdout);
ll a, b, n;
cin>>a>>b>>n;
while(n > 10)
{
n -= 10;
a *= 1e10;
a %= b;
}
for(int i = 0; i < n + 2; i++)
{
a *= 10;
if(i >= n - 1)
cout<<a / b;
a %= b;
}
return 0;
}