2025年全国青少年信息素养大赛复赛C++集训（15）：因子问题（题目及解析）

2025年全国青少年信息素养大赛复赛C++集训（15）：因子问题（题目及解析）

题目描述

任给两个正整数N、M，求一个最小的正整数a，使得a和(M-a)都是N的因子。

时间限制：10000

内存限制：65536

输入

包括两个整数N、M。N不超过1,000,000。

输出

输出一个整数a，表示结果。如果某个案例中满足条件的正整数不存在，则在对应行输出-1

样例输入

35 10

样例输出

5

AC代码

#include<bits/stdc++.h>
using namespace std;int n, m; // 输入的N和M
bool f = 0; // 标记是否找到符合条件的aint main() {cin >> n >> m;// 遍历可能的a值，从1到1e6。因为N不超过1e6，所以因子最大为Nfor(int a = 1; a <= 1000000; a++) {// 检查三个条件：a是N的因子，M-a是N的因子，且a必须小于M（保证M-a为正）if(n % a == 0 && n % (m - a) == 0 && m > a) {f = 1; // 找到解cout << a; // 输出最小的abreak; // 由于是从小到大遍历，找到后直接退出}}if(f == 0) { // 遍历完所有可能后仍未找到cout << -1;}return 0;
}

功能分析

1. 目标
   • 寻找最小的正整数a，使得a和(M-a)均为N的因子，且a < M。
2. 遍历范围
   • 由于题目中N的最大值为1e6，因此a的最大可能值不超过1e6。遍历1到1e6的所有整数。
3. 条件检查
   • n % a == 0：确保a是N的因子。
   • n % (m - a) == 0：确保(M - a)是N的因子。
   • m > a：确保M - a为正整数。

文末彩蛋：

关注并查看老师的个人主页，学习完整csp信奥赛完整系列课程： https://edu.csdn.net/lecturer/7901