当前位置: 首页 > news >正文

PTA 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)。

输出格式:

在一行中输出相应的最小的sn,其间以1个空格分隔。

输入样例:

31

输出样例:

3584229390681 15

代码实现: 

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

大致思路:

预备了解:

x:输入的不以5结尾的正奇数

count:光棍的位数

n:被除数

n/x:组成商的每一位

模拟除法图示:

1. 首先需要得到一个比输入的奇数x大的数(全部由1组成),比如:首先比31大的数是111

2. 得到第一位组成商的数字:111/31=3

3. 若是当前被除数不能整除除数,则需要找到下一个被除数,直至能整除就停止寻找

不能整除则留下余数,找下一个被除数:被除数需要增加1个1:比如111%31=18,下一个被除数是1111,则我们需要增加一个1

相当于增加1的效果:余数*10+1,比如18*10+1=181,同时统计一次记录位数的变化

这样即可得到组成商的每一位:余数*10+1/除数,比如181/31=5

代码解读:

part 1

    int x = 0;scanf("%d",&x);int n = 1;int count = 1;

n:让被除数 (光棍)从1开始

count:被除数是从1开始的,则光棍的位数开始是1位

part 2:找出首个比除数的被除数(光棍)

    while(n<x){n=n*10+1;count++;}

比如:最开始是1,1<31,则1->11,11<31,则11->111,111>31,while循环结束,此时光棍是111,位数是3

part 3:打印组成商的每一位数字

    while(1){printf("%d",n/x);n=n%x;if(n==0){break;}else{n=n*10+1;count++;}}

比如:经过上一个while循环后,被除数n是111,位数count是3

           此时首先打印出第一位组成商的数字:111/31=3

           然后判断余数是否为0,若为0则break结束循环,说明已经找到了能够整除的光棍

           若是余数不为0,则需要增加1个1,同时位数count+1,使得111变成1111

           模拟增加1的效果:余数*10+1,即它作为新的被除数去除以除数x,能够再次得到一位组成商的数字

            比如111%3=18,18*10+1=180(新的被除数),180/31=5(一位组成商的数字)

最后就是打印光棍的位数了

 printf(" %d",count);
http://www.lryc.cn/news/5379.html

相关文章:

  • 将小程序代码转成uni-app代码
  • C语言在游戏中播放音乐
  • 机器学习算法:随机森林
  • 如何做好多项目全生命周期的资源调配,提升资源利用效率?【橙子】
  • JVM - 内存分配
  • 【知识图谱论文】Bi-Link:通过转换器和提示的对比学习桥接来自文本的归纳链接预测
  • jieba+wordcloud 词云分析 202302 QCon 议题 TOP 关键词
  • 包管理工具-npm-npx-yarn-cnpm
  • go gin学习记录1
  • Docker常用命令
  • 论文写作——公式编辑器、latex表格、颜色搭配器
  • MySQL数据库12——视图(VIEW)
  • 第四代英特尔至强重磅发布,芯片进入下半场:软硬加速、绿色可持续
  • c++-运算符函数与运算符重载
  • 【MySQL Shell】8.9.3 修复 InnoDB ClusterSet 中的成员服务器和集群
  • 宝塔搭建实战php开源likeadmin通用管理pc端nuxt3源码(三)
  • 【C++】---Stack和Queue的用法及其模拟实现
  • Python GUI编程
  • 2023年浙江水利水电施工安全员精选真题题库及答案
  • Solon2 开发之插件,三、插件体外扩展机制(E-Spi)
  • 数据结构与算法(Java版) | 数据结构与算法的关系
  • 华科万维C++章节练习3_7
  • CHAPTER 5 Jenkins SonarQube
  • [AAAI 2023] Oral : Zero-shot 零样本/ Few-shot 少样本收录论文集合
  • 驱动开发 2.13
  • 【数据库】sql函数和多表关联查询
  • 6-周赛332总结
  • 嵌入式Qt 开发一个音乐播放器
  • 2023秋招万得集团AI算法岗面经分享
  • RoI Transformer论文翻译详解