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

2025/5/26 0:45:02 来源：https://blog.csdn.net/weixin_66461496/article/details/148190331 浏览: 次关键词：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

样例输出

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;
}

功能分析

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