题解 | #E# 因子问题

题目出自 51nod

题目描述

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

输入描述

包括两个整数 N、M。N 不超过 10^9。

输出描述

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

样例

输入

35 10

输出

5

算法

(暴力枚举 + 优化)

先暴力，TLE

    for(int i = 1; i <= m && i <= n; i++)
	{
		if(n % i == 0 && n % (m - i) == 0)
		{
			cout << i << endl;
			return 0;
		}
	}
    cout << res << endl;

优化1 i * i <= n WA了 说明答案是有可能大于 根号n 的

	for(int i = 1; i <= m && i * i <= n; i++)
	{
		if(n % i == 0 && n % (m - i) == 0)
		{
			cout << i << endl;
			return 0;
		}
	}
	cout << res << endl;

优化2 在for循环中加入

        int k = n / i;
		if(k < m && n % k == 0 && n % (m - k) == 0) res = k;

AC了

	for(int i = 1; i <= m && i * i <= n; i++)
	{
		if(n % i == 0 && n % (m - i) == 0)
		{
			cout << i << endl;
			return 0;
		}

		int k = n / i;
		if(k < m && n % k == 0 && n % (m - k) == 0) res = k;
	}
	cout << res << endl;

优化3 for循环条件改为 i <= m / 2 && i * i <= n 代码如下

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;

int main()
{
	int n, m;
	cin >> n >> m;

	int res = -1;
	for(int i = 1; i <= m / 2 && i * i <= n; i++)
	{
		if(n % i == 0 && n % (m - i) == 0)
		{
			cout << i << endl;
			return 0;
		}

		int k = n / i;
		if(k < m && n % k == 0 && n % (m - k) == 0) res = k;
	}
	cout << res << endl;

	return 0;
}