L1-046 整除光棍(模拟除法)

这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由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

C语言：

1、直接大数相除

while循环中思路是：

利用111除以31如果不能除尽则利用bachelor=bachelor*10+1;继续扩大111，使之成为1111再去除以31，循环往复直到能除尽。

111除以31有余数，bachelor=bachelor*10+1;得到1111

1111除以31有余数 ，bachelor=bachelor*10+1; 得到11111

11111除以31有余数 
......

但是这个题目如果直接使用直接的大数相除会超时，以下便是暴力除法代码，此代码运行结果正确，但是存在运行超时问题，我第一次提交的结果便是以下代码，报错后又进行修改。

#include <stdio.h>
int main()
{
    int x,remainder,count=0;
    scanf("%d",&x);
    long long bachelor=1,a,i,b;
    remainder=bachelor%x;
    while(remainder!=0)
    {
        bachelor=bachelor*10+1;
        remainder=bachelor%x;
    }
    a=bachelor;
    b=bachelor/x;
    for(i=a;i>0;i/=10)
    {
        count++;
    }
    printf("%lld %d\n",b,count);
    return 0;
}

2、模拟除法

思路还是原来的思路只是计算方法进行了简化

首先需要使bachelor的值大于输入的x（以31为例），如果没有此段直接使用下方的while循环也可以完成此项

但是printf输出的时候会在开端带2个零，因为bachelor初始值是1，小于31则商0余1

经过bachelor=bachelor*10+1;得到bachelor=11依旧小于31，同样商0余11

再次经过bachelor=bachelor*10+1;得到bachelor=111大于31，此时不再商0进入while循环中

因上述原因设立第一个while循环

模拟除法思路：

将商进行输出，将余数使用bachelor=bachelor*10+1;进行扩大后再除以31，以此循环往复，此方法比直接扩大相除运算量小，时间少。

#include <stdio.h>
int main(){
    long long bachelor=1;
    int count=1,x;
    scanf("%d",&x);
    while(bachelor<x){
        bachelor=bachelor*10+1;
        count++;
    }
    while(1){
        printf("%d",bachelor/x);
        bachelor=bachelor%x;
        if(bachelor==0){
            break;
        }else{
            bachelor=bachelor*10+1;
        }
        count++;
    }
    printf(" %d\n",count);
    return 0;
}