整除光棍求解

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的方式扩大光棍数来取余输入数  讲道理计算机计算次数应该也不多 为什么一直不出结果呢？ 求高手来解答以下）

1. #include <stdio.h>
   
2. 
   
3. int main()
   
4. {
   
5.     long long  s,temp = 1,x;
   
6.     int a,n = 1;
   
7. 
   
8.     scanf("%d",&a);
   
9.     while(1)
   
10.     {
    
11.         if(temp%a == 0)
    
12.         {
    
13.             x = temp/a;
    
14.             break;
    
15.         }
    
16.         temp = temp*10+1;
    
17.         n++;
    
18.     }
    
19. 
    
20.     printf("%lld %d",x,n);
    
21. 
    
22. 
    
23.     return 0;
    
24. }
    

复制代码

a905448839

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

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

a905448839

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

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


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

a905448839

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

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