题目大意

对于一个正整数 \(N\)，存在一个正整数 \(T\)，使得 \(\frac{N-\frac{1}{2}T}{N-T}\) 的值是正整数。

请输出所有可能的正整数 \(T\)（按从小到大的顺序排列）。

对于 \(100 \ \%\) 的数据，\(N \leq 10^{14}\)

解题思路

考虑分解这个上面那个式子，设 \(k\) 为 \(\frac{N-\frac{1}{2}T}{N-T}\) 的值：

\[\frac{N-\frac{1}{2}T}{N-T}=k \]

分数上下同乘 \(2\) 得：

\[\frac{2N-T}{2N-2T}=k \]

设 \(x=N-T\)，化简得：

\[\frac{x+N}{2x}=k \]

然后等式两边同乘 \(2\)，得：

\[\frac{2x+2N}{2x}=2k \]

化简得：

\[\frac{N}{x}+1=2k \]

\[\because k \ 为正整数且 \ 1 \ 为正整数 \]

\[\therefore \frac{N}{x} \ 为正整数 \]

\[\therefore x \ 为 \ N \ 的因子，即 \color{red}{\ N-T \ 为 \ N \ 的因子} \]

\[又 \because 2k \ 是偶数且 \ 1 \ 是奇数 \]

\[\therefore \frac{N}{x} \ 为奇数，即 \ \color{red}{\frac{N}{N-T} \ 为奇数} \]

再看回原式：

\[\frac{N-\frac{1}{2}T}{N-T}=k \]

\[\because T \ 为正整数且 \ N-T \ 为正整数 \]

\[\therefore N-\frac{1}{2}T \ 为正整数 \]

\[\therefore \color{red}{T \ 为偶数} \]

综上所述：

\[N-T \ 为 \ N \ 的因子，\frac{N}{N-T} \ 为奇数且 \ T \ 为偶数 \]

跑出所有因子判断即可。

时间复杂度 \(O(\sqrt{n})\)。

AC CODE

#include<bits/stdc++.h>
using namespace std;

#define int long long

int n;

int p[10000000], ans;

void js(int x)
{
	for(int i = 1; i <= sqrt(x); i ++)
	{
		if(x % i == 0)
		{
			if((x - i) % 2 == 0 && n / i % 2 == 1) p[++ans] = x - i;
			if(i * i != x && i != 1)
			{
				if((x - x / i) % 2 == 0 && n / (x / i) % 2 == 1)
					p[++ans] = x - x / i;
			}
		}
	}
}

signed main()
{
	scanf("%lld", &n);
	if(n == 1)
	{
		printf("0");
		return 0;
	}
	js(n);
	sort(p + 1, p + ans + 1);
	printf("%lld ", ans);
	for(int i = 1; i <= ans; ++i)
		printf("%lld ", p[i]);
	return 0;
}