Question

有多少个正整数有序对 $(x,y)$ 满足 $y<x\leq100$ ，并且 $\frac{x}{y}$ 与 $\frac{x+1}{y+1}$ 都是整数？

For how many ordered pairs of positive integers $(x,y),$ with $y<x\leq100,$ are both $\frac{x}{y}$ and $\frac{x+1}{y+1}$ integers?

答案

答案：85

知识点：整除性取整函数数对计数

难度评级：2060

小提示：

令 $x=ay$ ，并将 $x+1$ 模 $y+1$ 化简

Write $x=ay$ and reduce $x+1$ modulo $y+1$

大提示：

商 $a$ 必须形如 $1+t(y+1)$ ；计算 $t$ 的正整数取值数

The quotient $a$ must have the form $1+t(y+1)$ ; count the possible positive values of $t$

解答：

令 $x=ay$ 。模 $y+1$ 时， $y\equiv-1$ ，所以 $x+1$ 能被 $y+1$ 整除当且仅当 $a\equiv1\pmod {y+1}$ 。由于 $x>y$ ，可令 $a=1+t(y+1)$ ，其中 $t\geq1$ 。条件 $x\leq100$ 化为 $t\leq\left\lfloor\frac{100-y}{y(y+1)}\right\rfloor\text{。}$ 只有 $1\leq y\leq9$ 会有贡献，得到 $\begin{aligned}49+16+8&+4+3\\&+2+1+1+1\\&=85\end{aligned}\text{。}$

Write $x=ay.$ Modulo $y+1,$ we have $y\equiv-1,$ so $x+1$ is divisible by $y+1$ exactly when $a\equiv1\pmod {y+1}.$ Since $x>y,$ write $a=1+t(y+1)$ with $t\geq1.$ The bound $x\leq100$ becomes $t\leq\left\lfloor\frac{100-y}{y(y+1)}\right\rfloor.$ Only $1\leq y\leq9$ contribute, giving $\begin{aligned}49+16+8&+4+3\\&+2+1+1+1\\&=85.\end{aligned}$

1995 AIME 第 8 题

答案：85

难度评级：2060

小提示：

大提示：

解答：

其他年份的第 8 题