L1-046 整除光棍 (20分)

题目描述：

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

题目分析： 这题目第一眼看上去很难，感觉很棘手，但是读者只要仔细分析，就会发现，其实这只是一个初中的除法减法的运算原理罢了

如果你想用计算机的加减乘除来解题，这无非是错误的，怎么会这么轻易让你拿到20分呢，所以，正确的做法如下：

首先我们看到例题，x=31，我们先要找出一个大于x=31的光棍数，那就是111

我们对111和x=31进行，模运算，111%31=18，111/31=3，然后让1810再加一，即1810+1=181,181%31=26,181/31=5，然后再使26*10+1即261,261%31=13,261/31=8,我们使这两步循环下去，直到模运算==0，循环结束，而这一过程的除数就是题目要求的s

我们分析一下我们需要做些什么：

1. 找出一个大于x的光棍数
2. 需要有一个变量来存放位数，以便后面输出
3. 每循环一次，把循环的除数cout，节省空间（无需用字符串储存）
4. 循环结束后，把少输出的那一位输出，最后输出空格和位数位数变量

那么我们来看看代码吧：

#include<iostream>
using namespace std;
int main()
{
  int x;
  cin >> x;
  int temp = 1;
  int n = 1;
  //我们需要先找出一个大于x的光棍树
  while (temp < x) {
    temp = temp * 10 + 1;
    n++;
  }
  //然后进行循环
  while (temp % x != 0) {
    int t = temp / x;
    temp = temp % x;
    temp = temp * 10 + 1;
    n++;
    cout << t;
  }
  cout << temp / x;
  cout << " " << n;
}
复制代码