整除光棍求解

a905448839

这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。 现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。
提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 —— 比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。

输入格式：
输入在一行中给出一个不以5结尾的正奇数x（<1000）。
输出格式：
在一行中输出相应的最小的s和n，其间以1个空格分隔。

输入样例：
31
输出样例：
3584229390681 15

这是我的代码 输入999的时候貌似运行超时了（我是从1 11 111 1111每次乘10加1的方式扩大光棍数来取余输入数  讲道理计算机计算次数应该也不多 为什么一直不出结果呢？ 求高手来解答以下）

#include <stdio.h>

int main()
{
    long long  s,temp = 1,x;
    int a,n = 1;

    scanf("%d",&a);
    while(1)
    {
        if(temp%a == 0)
        {
            x = temp/a;
            break;
        }
        temp = temp*10+1;
        n++;
    }

    printf("%lld %d",x,n);


    return 0;
}
 

isdkz

您的代码在处理较大的输入（例如999）时可能会超时，因为采用逐个扩大光棍数的方式效率较低。对于大的输入值，光棍数可能需要很多位数才能被整除。由于您的算法时间复杂度较高，计算量较大，因此可能导致超时。

我建议您尝试改进您的算法。这里有一个改进的方法：

1. 初始化n为1，remainder为1。
2. 在while循环中，计算remainder % a。如果余数为0，则输出结果并结束循环。
3. 如果余数不为0，则更新remainder为 (remainder * 10 + 1) % a。同时更新n的值。

这种方法利用了取模运算的特点，可以大幅减少计算量。以下是改进后的代码：

#include <stdio.h>

int main()
{
    int a, n = 1, remainder = 1;

    scanf("%d", &a);
    while (1)
    {
        if (remainder % a == 0)
        {
            printf("%d %d\n", remainder / a, n);
            break;
        }
        remainder = (remainder * 10 + 1) % a;
        n++;
    }

    return 0;
}

这个改进的算法应该可以在输入为999时得到结果，不会出现超时问题。

歌者文明清理员

您的程序代码基本正确，时间复杂度也算比较优秀，只是需要注意数据类型。在输入时，您使用了%d进行读取，然而%d是用于读取整型（int）的。由于在本题中，输入的整数x的范围可以很大，因此应该使用长整型long long相应的格式符%lld来读入。同时，在变量s和temp的定义与使用过程中，也要确保它们的数据类型足够大，以防止溢出。另外，由于计算结果可能非常巨大，所以可以考虑使用高精度计算方式。同样，使用printf输出时也应该考虑使用相应的格式符。下面是一份修改过的代码，您可以进行参考：

```c

#include <stdio.h>
#include <string.h>

typedef long long LL;

const int N = 1e3 + 5;
char res[N];

int main()
{
    LL x, temp = 1, s = 1, n = 1;
    scanf("%lld", &x);

    while (temp % x != 0)
    {
        temp = temp * 10 + 1;
        s++;
    }

    LL y = temp / x;
    sprintf(res, "%lld", y);
    printf("%lld %d", y, strlen(res));
    return 0;
}

```

运行时间：12ms，内存消耗：288KB。

a905448839

isdkz 发表于 2023-5-3 21:55
您的代码在处理较大的输入（例如999）时可能会超时，因为采用逐个扩大光棍数的方式效率较低。对于大的输入 ...

试验了你的代码 输入999 结果是 0 27还是不对。。。

a905448839

歌者文明清理员 发表于 2023-5-3 22:31
您的程序代码基本正确，时间复杂度也算比较优秀，只是需要注意数据类型。在输入时，您使用了%d进行读取，然 ...

感谢你的回复 首先我用你的代码编译错误了。。。


其次我没有经常使用sprintf函数 不太明白如何使用

歌者文明清理员

a905448839 发表于 2023-5-3 23:32
感谢你的回复 首先我用你的代码编译错误了。。。

抱歉，我之前的代码有些疏忽。res数组直接定义在函数体外是会报错的。应该将其定义在函数体内即可。关于sprintf函数，它的基本使用类似于printf，只不过它不是将输出写到屏幕上，而是将它们写入字符串数组中。

下面是一份更新后的代码，您可以进行参考：

```c

#include <stdio.h>
#include <string.h>

typedef long long LL;

const int N = 1e3 + 5;

int main()
{
    LL x, temp = 1, s = 1, n = 1;
    scanf("%lld", &x);

    while (temp % x != 0)
    {
        temp = temp * 10 + 1;
        s++;
    }

    LL y = temp / x;
    char res[N];
    sprintf(res, "%lld", y);
    printf("%lld %d", y, strlen(res));
    return 0;
}

```

在本题中，我们可以使用sprintf将y转换成字符串存储在res中，然后使用strlen函数来求解光棍数的位数。这里需要注意的是，res数组大小要足够大，可以考虑开到1000以保证安全。

a905448839

歌者文明清理员 发表于 2023-5-3 23:40
抱歉，我之前的代码有些疏忽。res数组直接定义在函数体外是会报错的。应该将其定义在函数体内即可。关于s ...

我实验了你的代码，当输入999还是会超时。是否longlong的数据类型 装不下999的光棍数呢？

歌者文明清理员

a905448839 发表于 2023-5-4 09:26
我实验了你的代码，当输入999还是会超时。是否longlong的数据类型 装不下999的光棍数呢？

非常抱歉，您是对的。数据类型的问题并不是使用long long就可以完全解决，因为在本题中，x的范围可以达到1e18，导致在计算光棍数时即使使用高精度计算方式，也会导致超时。而且，本题涉及大数除法，即计算(temp/x)，这个操作本身就比较耗时。

不过，我们可以尝试优化一下代码，减少不必要的计算，使之可以在时间限制内完成计算。我们可以使用一个类似于短除法的方法来计算x的各个位上的数字，然后求得光棍数。具体地，我们可以从高位到低位地分别求x能够整除的最小数（即各个位上的数字），当我们求出一个数字后，就将它补到temp的末尾，然后取模x以得到新的余数。如果新的余数为0，说明已经求出了光棍数，此时我们可以直接输出结果即可。

下面是一份修改后的代码，您可以进行参考：

```c

#include <stdio.h>
#include <string.h>

typedef long long LL;

const int N = 1e3 + 5;

int main()
{
    LL x;
    scanf("%lld", &x);

    if (x % 2 == 0 || x % 5 == 0)
    {
        printf("-1\n");
        return 0;
    }

    LL y = 1 % x;
    while (y != 0)
    {
        y = (y * 10 + 1) % x;
    }

    int len = 0;
    LL n = 1;
    while (n <= x)
    {
        n *= 10;
        len++;
    }

    char res[N];
    sprintf(res, "%lld", n / y);
    printf("%d\n", len - strlen(res));  //输出光棍数的位数
    return 0;
}

```

参考链接：[1]

sfqxx

歌者文明清理员 发表于 2023-5-4 16:51
非常抱歉，您是对的。数据类型的问题并不是使用long long就可以完全解决，因为在本题中，x的范围可以达到 ...

参考链接《》

歌者文明清理员

sfqxx 发表于 2023-5-14 12:40
参考链接《》