PAT--L1-046. 整除光棍

女爷i 2022-06-14 11:50 161阅读 0赞

题目链接：[https://www.patest.cn/contests/gplt/L1-046][https_www.patest.cn_contests_gplt_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

就是模拟纸上的除法过程：除-->余数--->余数进位继续除--->......--->余数为 0 ，得到答案

代码：

#include <iostream>
    using namespace std;
    typedef long long ll;
    
    int main() {
        ll s, ans = 1;
        int n = 1; // 刚开始一个 1 计入位数 
        cin >> s;
        // 得到第一个不小于 s 的数，防止开始除的时候输出的结果为 0 
        while(ans < s) {
            ans = ans*10 + 1; 
            n++;
        }
        while(1) {
            // 能整除就输出并且结束 
            if(ans % s == 0) {
                cout << ans / s;
                break;
            // 不能整除就输出除的结果，并用余数进位继续除
            } else {
                cout << ans / s;
                ans %= s;
                ans = ans*10 + 1; 
                n++;
            }
        }
        cout << " " << n << endl;
    
    
        return 0;
    }

[https_www.patest.cn_contests_gplt_L1-046]: https://www.patest.cn/contests/gplt/L1-046