这道题请大家帮忙看一下，谢谢！ - 编程论坛

#2

rjsp2025-04-30 20:29

1)“第一个大于等于a，且是X的倍数”的数是 (a/X)向上取整，然后乘以x
“第一个大于等于a，且是X的倍数，且不是100X倍数”的数是 (a/X)向上取整，如果它是100的倍数的话，再加一，然后乘以X

2)设第一个【X数】是1*X，那么Y是第几个【X数】？
答：因为每连续的100个【X的倍数】要被舍弃掉一个100X的倍数，所以Y是第 Y/X - Y/X/100 个【X数】
   例如 1X 是第 1 个【X数】
   例如 99X 是第 99 个【X数】
   例如 101X 是第 100 个【X数】
错误的是，按上面的公式求得 -1X 是第 -1 个【X数】，这就不对了，既然设 1X 是第一个【X数】，那么 -1X 就应该是第0个【X数】。也就是负数的话，需要增加1。

3)求第n个【X数】是多少？也就是求2)的反函数
解：设结果是 (100p+q)X，其中 0<q<100
   那么按照2)的结论有 (100p+q) - (100p+q)/100 = n，化简得 (n-q)/99 = p
   例如求第100个【X数】，因为 (100-1)/99=1，即p=1，1=1，结果是 (1*100+1)X = 101X
   例如求第99个【X数】，因为 (99-99)/99=1，即p=0，q=99，结果是 (0*100+99)X = 99X
   例如求第0个【X数】，因为 (0-99)/99=-1，即p=-1，q=99，结果是 (-1*100+99)X = -X
   例如求第-1个【X数】，因为 (-1-98)/99=-1，即p=-1，q=98，结果是 (-1*100+98)X = -2X

程序代码：

#include <iostream>
using namespace std;

int main( void )
{
    size_t T;
    cin >> T;
    while( T-- )
    {
        int x, a, b;
        cin >> x >> a >> b;

        // 求【第一个大于a的【x数】】是x的几倍
        int t = (a>=0)
            ? (a+x-1)/x + ((a+x-1)/x%100==0)
            : a/x + (a/x%100==0);

        // 求 tx 是第几个【x数】
        int m = t - t/100;
        m += m<0;


        // 求第 n 个【x数】是多少
        int n = m + (b-1);
        int q = n%99==0 ? 99 : (n%99+99)%99;
        int p = (n-q)/99;
        int result = (p*100 + q)*x;
        cout << result << '\n';
    }
}

#3

yywx20232025-05-01 15:54

回复 2楼 rjsp

谢谢！十分感谢您的指导，谢谢！

#4

rjsp2025-05-02 11:12

上面是“设第一个【X数】是1*X，”，假如改为“设第0个【X数】是1*X，”的话，且放宽到允许用浮点数

程序代码：

#include <iostream>
#include <cmath>
using namespace std;

int main( void )
{
    size_t T;
    cin >> T;
    while( T-- )
    {
        int x, a, b;
        cin >> x >> a >> b;

        // 求【第一个大于a的【x数】】是x的几倍
        // a/x 向上取整，若为100的倍数，再增一
        int t = (int)ceil(a*1.0/x);
        if( t%100 == 0 )
            t += 1;

        // 求 tx 是第几个【x数】
        // t*99/100 向下取整
        int m = (int)floor( 99/100.0 * t );

        // 求第 n 个【x数】是多少
        // t*100/99 向下取整，再增一
        int n = m + (b-1);
        int result = 1 + (int)floor( 100/99.0 * n );
        cout << result*x << '\n';
    }
}

#5

XXGGZZQQ2025-05-17 10:14

一下是二分答案的程序（配有详细注释,写的比较匆忙，可能有误）
```
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; // 使用LL代替long long，方便书写

int main()
{
    int T; // 询问次数
    scanf("%d", &T);
    while (T--) // 处理每个询问
    {
        int X, a, b;
        scanf("%d%d%d", &X, &a, &b); // 读入X, a, b

        // 计算起始的k值，满足k*X >= a
        LL start_k;
        if (a % X == 0)
        {
            start_k = a / X; // 如果a是X的倍数，直接取商
        }
        else
        {
            // 如果a是正数且不是X的倍数，需要向上取整
            if (a > 0)
            {
                start_k = a / X + 1;
            }
            else
            {
                // 如果a是负数，除法会自动向下取整，结果已经是满足k*X >= a的最小值
                start_k = a / X;
            }
        }

        // 调整start_k，确保不是100的倍数（因为100倍数的数不算X数）
        LL adj_k = start_k; // adj_k表示调整后的起始k值
        if (adj_k % 100 == 0)
        {
            adj_k++; // 如果起始k是100的倍数，跳过它
        }

        // 二分查找：寻找第b个有效的k值（即不是100的倍数）
        LL left = adj_k;   // 左边界
        LL right = adj_k + 1LL * b * 100; // 右边界（足够大）
        while (left < right)
        {
            LL mid = (left + right) / 2; // 中间值

            // 计算[left, mid]区间内的有效k的数量
            // 总共有 (mid - adj_k + 1) 个数
            // 减去其中是100的倍数的数的个数
            LL total = mid - adj_k + 1; // 区间内总共有多少个数
            LL invalid = (mid / 100) - ((adj_k - 1) / 100); // 区间内是100的倍数的数的个数
            LL cnt = total - invalid; // 有效数的数量

            if (cnt < b)
            {
                // 如果有效数不够，需要扩大右边界
                left = mid + 1;
            }
            else
            {
                // 否则缩小右边界
                right = mid;
            }
        }

        // 最终结果就是left对应的数（left是满足条件的第b小的k值）
        LL ans = left * X;
        printf("%lld\n", ans);
    }
}

#6

yywx20232025-05-17 22:44

回复 5楼 XXGGZZQQ

谢谢！