小红的正整数构造【牛客tracker 每日一题】

小红的正整数构造时间限制1秒 空间限制256M知识点模拟网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一个闭区间[ l , r ] [l,r][l,r]以及一个正整数x xx。请在区间内找到一个整数y yy满足y yy是x xx的倍数即y ≡ 0 ( m o d x ) y≡0(\mod x)y≡0(modx)。若存在多个满足条件的y yy输出任意一个若不存在输出− 1 −1−1。输入描述在一行上输入三个整数l , r , x ( 1 ≦ l ≦ r ≦ 10 2 ; 1 ≦ x ≦ 10 2 ) l,r,x(1≦l≦r≦10^2; 1≦x≦10^2)l,r,x(1≦l≦r≦102;1≦x≦102)——区间左右端点与基准倍数。输出描述若存在满足条件的整数y yy在一行上输出y yy否则输出− 1 −1−1。如果存在多个答案可以输出任意一个系统会自动判断其正确性。示例1输入6 10 3输出6说明6 66与9 99均为3 33的倍数本题输出了6 66。示例2输入8 9 5输出-1说明区间内不存在5 55的倍数因此输出− 1 −1−1。解题思路本题是基础的区间倍数查找问题由于数据范围极小采用线性遍历枚举的方法即可高效解决。问题分析需要在闭区间[ l , r ] [l, r][l,r]中找到任意一个能被x xx整除的正整数若不存在则返回 -1存在多个时输出任意一个均可。算法选择由于l ll和r rr最大仅为 100区间长度不超过 100直接遍历区间内每个整数逐一判断是否为x xx的倍数实现最简单且不易出错完全满足时间要求。执行逻辑从区间左端点l ll开始向右遍历找到第一个满足i % x 0的数立即输出并结束程序若遍历完整个区间仍未找到符合条件的数输出 -1。复杂度分析时间复杂度为O ( r − l 1 ) O(r-l1)O(r−l1)最坏情况仅 100 次运算远低于时间限制。总结核心逻辑线性遍历区间内所有整数通过取模运算判断是否为x的倍数找到即提前返回遍历结束无结果则输出-1。关键操作取模整除判定、命中即提前终止程序。效率保障数据范围极小暴力枚举完全满足要求代码简洁直观无额外开销。代码简要说明变量定义变量a、b、c分别存储区间左端点、右端点和基准倍数x。输入读取使用scanf读入三个整数保证输入效率。遍历查找从左端点a到右端点b循环遍历每个数若当前数能被c整除则立即输出该数并直接返回结束程序保证输出区间内第一个符合条件的倍数。无结果处理循环正常结束说明区间内无符合条件的数输出 -1。提前终止优化找到第一个符合条件的数就直接退出无需遍历剩余区间进一步减少运算量。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll a,b,c;scanf(%lld%lld%lld,a,b,c);for(ll ia;ib;i)if(i%c0){printf(%lld,i);return0;}printf(-1);return0;}