B. Div Times Mod

问题描述:

Vasya likes to solve equations. Today he wants to solve (x div k)⋅(xmodk)=n, where div and mod stand for integer division and modulo operations (refer to the Notes below for exact definition). In this equation, k and n are positive integer parameters, and x is a positive integer unknown. If there are several solutions, Vasya wants to find the smallest possible x. Can you help him?

(其实就是已知n,k,(x/k)*(x%k)=n,求x的值)

输入内容:

(The first line contains two integers n and k (1≤n≤10^6, 2≤k≤1000))

输出内容:x

样例:


http://codeforces.com/contest/1085/problem/B

由题可知:n不为0,所以x肯定大于k

第一思路:由k+1开始遍历x的值,但失败了,因为当n的值很大时,x也很大,要遍历很多次,最终导致超时;

第二思路:将x%k当作新的值i,这样最多只需遍历k-1次数字就可以找到i,而x=(\frac{n}{i} )\times k+i,所以,代码如下:


所以说,很多次遇到带有余数的场景时,一定要对它多加利用,因为题目往往喜欢设置很大的数字,此时不用余数计算来遍历就特别容易超时。。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容