博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【数学】【P5076】 Tweetuzki 爱整除
阅读量:5869 次
发布时间:2019-06-19

本文共 691 字,大约阅读时间需要 2 分钟。

Description

对于一个数 \(k\),找到任意一个 \(x\),满足 \(0~\leq~k~\leq~x~\leq~10^{18}\) 且对于任意一个 \(x\) 进制数,把该数字各数位上的数字相加,最后得出的值若可以被 \(k\) 整除,则该数可以被 \(k\) 整除。

Input

输入仅包含一行一个整数 \(k\)

Output

输出一行一个整数代表任意一个符合要求的答案

Hint

\(2~\leq~k~\leq~10^9\)

Solution

考虑题目中给出的例子,各个位上的数加起来被三整除的数能够被三整除,我们来分析一下原因:

不妨设这个数 \(x\) 是两位数,否则将两位看成一位做数学归纳:

\(x~=~10~a~+~b\),则

\[x~=~10~a~+~b~=~a~+~b~+~9~a\]

\[x~\equiv~0~(\bmod~3)~,~9a~\equiv~0~(\bmod~3)\]

于是

\[a~+~b~\equiv~0~(\bmod~3)\]

类似的可以发现,当一个进制数相邻两位的差值可以被 \(k\) 整除时,该数可以被 \(k\) 整除。

设这是个 \(x\) 进制数,则更高一位减更低一位的差值为 \(x~-~1\)

于是 \(x~-~1~\equiv~0~(\bmod~k)\)

任意输出一个 \(x\) 即可。最简单的当然是输出 \(k~+~1\)

Code

a = int(input())print(a + 1)

转载于:https://www.cnblogs.com/yifusuyi/p/10091223.html

你可能感兴趣的文章
grep 零宽断言
查看>>
被神话的大数据——从大数据(big data)到深度数据(deep data)思维转变
查看>>
修改校准申请遇到的问题
查看>>
python大佬养成计划----win下对数据库的操作
查看>>
监控软件zabbix之安装
查看>>
Exchange Server 2016 独立部署/共存部署 (七)—— DAG功能测试
查看>>
Linux 进程中 Stop, Park, Freeze【转】
查看>>
Spark修炼之道(基础篇)——Linux大数据开发基础:第九节:Shell编程入门(一)...
查看>>
Duplicate Symbol链接错误的原因总结和解决方法[转]
查看>>
适配器模式
查看>>
建立低权限的ftp帐号
查看>>
htpasswd
查看>>
微软整合实验(七):布署Exchange2010 Mailbox高可用(DAG)
查看>>
spring定时器----JobDetailBean
查看>>
我的友情链接
查看>>
XP下如何删除附件中的游戏组件
查看>>
我的友情链接
查看>>
emma的几个不足之处
查看>>
Java工具类——UUIDUtils
查看>>
使用Node搭建reactSSR服务端渲染架构
查看>>