Vasya's Function

题目描述

Vasya is studying number theory. He has denoted a function $f(a, b)$ such that:

• $f(a, 0)=0$;
• $f(a, b)=1+f(a, b-(a, b))$, where $(a, b)$ is the greatest common divisor of $a$ and $b$.

Vasya has two numbers $x$ and $y$, and he wants to calculate $f(x, y)$. He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.

题意概述

函数$f(a, b)$的定义如下：

$$
\begin{align}
f(a, 0)&=0 \\
f(a, b)&=1+f(a, b-(a, b))
\end{align}
$$

给定$x, y$，求$f(x, y)$。

数据范围：$1 \le x, y \le 10^{12}$。

算法分析

有个显然的结论：$f(a, b)=f(ka, kb) \ (k \gt 0)$。所以只需要考虑$(a, b)=1$的情况。

设$(x, y)=1$，由于$x$始终不变，因此先将$x$分解质因数。质因子最多只有$12$个，因为$2 \times 3 \times 5 \times 7 \times \cdots \times 31 \times 37 \gt 10^{12}$。找出最大的$s$满足$s \lt y$且$s$是$x$某个质因子的倍数，将答案加上$y-s$，并令$y=s$。将$x, y$同时除以$(x, y)$，问题转化成了一个更小的子问题，可以迭代处理。

代码

import std.stdio;
import std.math;

static immutable int N = 13;

uint top;
long x, y, p, q, ans;
long[N] prime, cnt;

long gcd(long a, long b) {
  return b ? gcd(b, a % b) : a;
}

int main() {
  readf(" %d %d", &x, &y);
  p = x, q = cast(long) sqrt(real(x));
  for (int i = 2; i <= q; ++ i) {
    while (! (p % i)) {
      p /= i;
      if (prime[top] == i) ++ cnt[top];
      else prime[++ top] = i, cnt[top] = 1;
    }
  }
  if (p > 1) prime[++ top] = p, cnt[top] = 1;
  while (y) {
    long max = 0;
    for (int i = 1; i <= top; ++ i)
      if (cnt[i])
        if (y / prime[i] * prime[i] > max)
          max = y / prime[i] * prime[i];
    ans += y - max, y = max;
    long g = gcd(x, y);
    x /= g, y /= g;
    for (int i = 1; i <= top; ++ i)
      while (! (g % prime[i]))
        g /= prime[i], -- cnt[i];
  }
  writeln(ans);
  return 0;
}