题解 CF1089F Fractions
次阅读
4 min read
数论渣渣做数论题。
题目要求的等价于找出若干个 的约数(除了 )使得存在给每个配上一个系数让和为 。
想想什么情况没有解,若选的约数都不互质那没救了,因为 肯定和 是互质的,而选出来的这些数都是 的约数,它们加起来肯定是和 有除了 以外的因子的,而 和 没有,所以不可能。而若一个数只有单一质因子,那选出来的肯定互质不了。
那么一个质因子不行就想想两个可不可以做到。
就是要求出一个 , 且满足 。将 移到一边,变成 ,那么要求就变成要让这个式子的里的每个数都是正整数是否可行。因为 , 所以 ; 因为是整数,所以 。
对于后面一个条件,因为 是 的约数,所以 也得是 的约数,又因为 和 是互质的,所以 在模 意义下循环节长度是 ,所以当 取 时 恰好都被取到一次,也就是一定会有一个 。
再看前一个条件,等价于 , 因为 在 范围内时一定有满足后面条件的,所以一定存在满足条件的同时满足 , 因为 , 所以满足另一个条件的也一定满足 。
所以题目里什么 都是骗人的,只要两个就可以了。
具体地,先暴力找出 的所有质因子,然后选俩质因子枚举并判断是否满足条件就好了。
代码。
#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;
}