题解 CF1089F Fractions

数论渣渣做数论题。

题目要求的等价于找出若干个 nn 的约数(除了 11)使得存在给每个配上一个系数让和为 n1n-1

想想什么情况没有解,若选的约数都不互质那没救了,因为 n1n-1 肯定和 nn 是互质的,而选出来的这些数都是 nn 的约数,它们加起来肯定是和 nn 有除了 11 以外的因子的,而 n1n-1nn 没有,所以不可能。而若一个数只有单一质因子,那选出来的肯定互质不了。

那么一个质因子不行就想想两个可不可以做到。

就是要求出一个 ax+by=n1ax + by = n-1, 且满足 x,ynx, y | n。将 bb 移到一边,变成 b=n1axyb = \frac{n-1-ax}{y},那么要求就变成要让这个式子的里的每个数都是正整数是否可行。因为 y>0y > 0, 所以 n1ax>0n-1-ax > 0; 因为是整数,所以 yn1axy | n-1-ax

对于后面一个条件,因为 yynn 的约数,所以 ax+1ax+1 也得是 yy 的约数,又因为 xxyy 是互质的,所以 axax 在模 yy 意义下循环节长度是 yy,所以当 aa[0,y1][0, y-1][0,y1][0, y-1] 恰好都被取到一次,也就是一定会有一个 axy1(mody)ax \equiv y-1 \pmod y

再看前一个条件,等价于 ax<n1ax < n-1, 因为 aa[0,y1][0, y-1] 范围内时一定有满足后面条件的,所以一定存在满足条件的同时满足 ax<(y1)x<xyxax < (y-1)x < xy - x, 因为 xy=n,x>1xy = n, x > 1, 所以满足另一个条件的也一定满足 ax<n1ax < n-1

所以题目里什么 10510^5 都是骗人的,只要两个就可以了。

具体地,先暴力找出 nn 的所有质因子,然后选俩质因子枚举并判断是否满足条件就好了。

代码。

#include <cstdio>
int n, fac[105], m;
int main() {
	scanf("%d", &n);
	int n_ = n;
	for(int i = 2; i*i <= n; i++)	
		if(n_ % i == 0) {
			fac[++m] = i;
			while(n_ % i == 0) n_ /= i;
		}
	if(n_ != 1) fac[++m] = n_;
	if(m <= 1) return puts("NO"), 0;
	
	puts("YES\n2");
	
	int a, b, x = fac[1], y = fac[2];
	for(a = 1; a <= y-1; a++)
		if((a*x+1) % y == 0) { b = (n-1-a*x)/y; break; }
	printf("%d %d\n%d %d", a, n/x, b, n/y);
	return 0;
}