题意分析

题目要求计算有理数在$7$进制下的展开形式，并提取小数点后指定位置范围内的数字。具体规则如下：

1. $7$进制展开：

   • 给定有理数$\frac{n}{d}$（$0 \leq n \leq 5,000$，$1 \leq d \leq 5,000$），计算其在7进制下的小数部分。
   • 例如：
     • $\frac{1}{5}$的$7$进制展开为$0.12541..._7$。
     • $\frac{33}{4}$的$7$进制展开为$11.15151..._7$。

2. 数字提取：

   • 输入指定起始位置$b$和结束位置$e$（$0 \leq b, e \leq 250$，$0 \leq (e - b) \leq 20$）。
   • 位置$0$表示小数点后的第一位。
   • 输出从位置$b$到$e$的数字序列。

解题思路

关键点分析

1. 7进制小数展开：

   • 使用长除法计算$\frac{n}{d}$的$7$进制小数部分。
   • 每次除法步骤：
     1. 将当前余数乘以$7$。
     2. 计算商（即当前小数位的数字）。
     3. 更新余数为新的余数。
     4. 重复直到达到所需精度。

2. 数字提取：

   • 需要计算足够多的小数位以覆盖位置$e$。
   • 存储小数位的数字序列，直接提取$b$到$e$的子序列。

3. 边界处理：

   • 如果$n=0$，则小数部分全为$0$。
   • 如果$\frac{n}{d}$是整数，则小数部分全为$0$。

解决步骤

1. 输入处理：

   • 读取问题集数量。
   • 对每个问题集，读取$n$、$d$、$b$、$e$。

2. 7进制展开计算：

   • 初始化余数为$n \mod d$。
   • 重复长除法直到计算到位置$e$的小数位：
     • 余数$= \text{余数} \times 7$。
     • 当前数字$= \text{余数} // d$。
     • 余数$= \text{余数} \mod d$。
     • 如果余数为$0$，则后续小数位全为$0$。

3. 数字提取与输出：

   • 存储小数位的数字序列。
   • 提取从$b$到$e$的子序列作为结果。
   • 格式化输出。

算法复杂度

• 时间复杂度：$O(e)$，每个问题集最多计算$250$位小数。
• 空间复杂度：$O(e)$，存储小数位的数字序列。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
 
int main()
{
    int n,num,p,i,a,b,l,r;
    int ans[5050];
    scanf("%d",&n);
    for(num=1;num<=n;num++)
    {
        memset(ans,0,sizeof(ans));
        scanf("%d %d %d %d",&a,&b,&l,&r);
        p=a;
        a=a%b;
        int k=0;
        while(k<=r)
        {
            a=a*7;
            ans[k]=a/b;
            a=a%b;
            k++;
        }
        printf("Problem set %d: %d / %d, base 7 digits %d through %d: ",num,p,b,l,r);
        for(i=l;i<=r;i++)
        {
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
 
}