uva 10555 – Dead Fraction)(数论)

全栈程序员站长

发布于 2022-07-10 10:36:57

2060

发布于 2022-07-10 10:36:57

文章被收录于专栏：全栈程序员必看全栈程序员必看

大家好，又见面了，我是全栈君。

题目链接：uva 10555 – Dead Fraction

题目大意：给出一个小数，从…開始能够是不论什么数字，可是保证是无限循环小数。将该小数用分式的形式表示，而且要求分母尽量大。

解题思路：这题主要是怎么将无限循环小数转换成分式，这种：

有小数0.abcdEEE，未循环部分长4。循环节为E，E的长度为i(如果)
abcd+E999…(i位9）10i

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int maxn = 105;
const ll INF = 0x3f3f3f3f3f3f3f;

char s[maxn];

ll gcd (ll a, ll b) {
    return b ? gcd(b, a%b) : a; } int main () { while (scanf("%s", s) == 1 && strcmp(s, "0")) { int len = strlen(s)-5; ll ansu, ansd = INF; for (int i = 0; i < len; i++) s[i] = s[i+2]; for (int i = 0; i < len; i++) { ll d = 1, u = 0; for (int j = 0; j < i; j++) { d = d * 10; u = u * 10 + s[j] - '0'; } ll x = 0, y = 0; for (int j = i; j < len; j++) { x = x * 10 + s[j] - '0'; y = y * 10 + 9; } d = d * y; u = u * y + x; ll g = gcd(d, u); u /= g; d /= g; if (d < ansd) { ansd = d; ansu = u; } } printf("%lld/%lld\n", ansu, ansd); } return 0; }

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/115675.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022年2月1，如有侵权请联系 cloudcommunity@tencent.com 删除

java