小红的正整数构造【牛客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。

解题思路

本题是基础的区间倍数查找问题，由于数据范围极小，采用线性遍历枚举的方法即可高效解决。

1. 问题分析：需要在闭区间[ l , r ] [l, r][l,r]中找到任意一个能被x xx整除的正整数，若不存在则返回 -1，存在多个时输出任意一个均可。
2. 算法选择：由于l ll和r rr最大仅为 100，区间长度不超过 100，直接遍历区间内每个整数，逐一判断是否为x xx的倍数，实现最简单且不易出错，完全满足时间要求。
3. 执行逻辑：从区间左端点l ll开始向右遍历，找到第一个满足i % x == 0的数立即输出并结束程序；若遍历完整个区间仍未找到符合条件的数，输出 -1。
4. 复杂度分析：时间复杂度为O ( r − l + 1 ) O(r-l+1)O(r−l+1)，最坏情况仅 100 次运算，远低于时间限制。

总结

核心逻辑：线性遍历区间内所有整数，通过取模运算判断是否为x的倍数，找到即提前返回，遍历结束无结果则输出-1。
关键操作：取模整除判定、命中即提前终止程序。
效率保障：数据范围极小，暴力枚举完全满足要求，代码简洁直观无额外开销。

代码简要说明

1. 变量定义：变量a、b、c分别存储区间左端点、右端点和基准倍数x。
2. 输入读取：使用scanf读入三个整数，保证输入效率。
3. 遍历查找：从左端点a到右端点b循环遍历每个数，若当前数能被c整除，则立即输出该数并直接返回，结束程序，保证输出区间内第一个符合条件的倍数。
4. 无结果处理：循环正常结束说明区间内无符合条件的数，输出 -1。
5. 提前终止优化：找到第一个符合条件的数就直接退出，无需遍历剩余区间，进一步减少运算量。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;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 i=a;i<=b;i++)if(i%c==0){printf("%lld",i);return0;}printf("-1");return0;}