Maksimuma çatdır bunu! (Həll təhlili)

Gəlin, $n$ və $m$ sabit olduğu halda $Z$ -dən olan $i, j$ üçün $f (i, j) = i / n - j / m$ f(i, j) = i / n - j / m ifadəsinin hansı qiymətləri ala biləcəyinə baxaq. Məsələn, $f (n, m) = n / n - m / m = 0$ f(n, m) = n / n - m / m = 0.

Məsələn, $f (i, j) = i /3 - j /5$ f(i, j) = i / 3 - j / 5 funksiyasını nəzərdən keçirək. Onda

f (i, j) = \frac{5 i - 3 j}{15}

f(i, j) = {5i - 3j \over 15}

Genişlənmiş Evklid alqoritminə görə həmişə belə tam $i$ və $j$ var ki, $i /3 - j /5 = 1$ i / 3 - j / 5 = 1. Deməli, bu ifadənin ala biləcəyi ən kiçik müsbət dəyər $1/15$ -dir. Bundan çıxır ki, bu ifadə $k /15$ şəklində bütün mümkün dəyərləri ala bilər, burada $k \in Z$ k \in Z.

Teorem. Əgər $f (i, j) = i / n - j / m$ f(i, j) = i / n - j / m-dirsə, onda bu funksiya $k / E K Q (n, m)$ k / EKQ(n, m) şəklindəki dəyərləri alır, burada $k \in Z$ k \in Z.

Sübut. Doğrudan da,

f (i, j) = i / n - j / m = \frac{i \cdot m - j \cdot n}{n \cdot m} = \frac{( i \cdot m ) / E B O B ( n , m ) - ( j \cdot n ) / E B O B ( n , m )}{( n \cdot m ) / E B O B ( n , m )} = \frac{i \cdot ( m / E B O B ( n , m )) - j \cdot ( n / E B O B ( n , m ))}{E K Q ( n , m )}

f(i, j) = i / n - j / m = {i \cdot m - j \cdot n \over n \cdot m} = \\ {(i \cdot m) / EBOB(n, m) - (j \cdot n) / EBOB(n, m) \over (n \cdot m) / EBOB(n, m)} = {i \cdot (m / EBOB(n, m)) - j \cdot (n / EBOB(n, m)) \over EKQ(n, m)}

Çünki $m / E B O B (n, m)$ m / EBOB(n, m) və $n / E B O B (n, m)$ n / EBOB(n, m) ədədləri qarşılıqlı sadədir, həmişə belə $i$ və $j$ var ki, kəsrin surəti $1$ -ə bərabər olsun. Deməli, $f (i, j)$ f(i, j) funksiyası $k / E K Q (n, m)$ k / EKQ(n, m) şəklindəki bütün mümkün dəyərləri ala bilər, burada $k \in Z$ k \in Z.

İndi orijinal funksiyanı nəzərdən keçirək

f (t) = mi n_{i, j \in Z} ∣ \frac{i}{n} - \frac{j}{m} + t ∣

f(t) = min_{i,j \in Z} |{i \over n} - {j \over m} + t|

Onun qiymətləri $t$ nöqtəsindən $k / E K Q (n, m), k \in Z$ k / EKQ(n, m), k \in Z şəklindəki ən yaxın nöqtəyə olan məsafələrdir. Funksiyanın $f (t)$ maksimumlaşdırılması üçün $t$ dəyərini seçmək lazımdır ki, bu dəyər $k / E K Q (n, m)$ k / EKQ(n, m) və $(k + 1) / E K Q (n, m)$ (k + 1) / EKQ(n, m) arasında dəqiq mərkəzdə olsun, burada $k$ tam ədəddir. Bu nöqtədə funksiyanın qiyməti $1/2 \cdot E K Q (n, m)$ 1 / 2 \cdot EKQ(n, m)-ə bərabərdir ki, bu da cavab olacaq.

Misal

Qoy $f (t) = mi n_{i, j \in Z} ∣ \frac{i}{3} - \frac{j}{5} + t ∣$ f(t) = min_{i,j \in Z} |{i \over 3} - {j \over 5} + t| olsun. Aşkar ki, $f (0) = 0$ f(0) = 0. $f (1/15) = 0$ f(1 / 15) = 0 bərabərliyi doğru olduğu halda, belə $i$ və $j$ var ki, $i /3 - j /5 = - 1/15$ i / 3 - j / 5 = -1 / 15 (məsələn, $i = 1, j = 2$ i = 1, j = 2). Bu, həmçinin $f (k /15) = 0$ f(k / 15) = 0 olduğu halda, bu $k \in Z$ k \in Z-dir.

Ancaq $f (k /15 + 1/30) = 1/30$ f(k / 15 + 1 / 30) = 1 / 30, və bu funksiyanın olabiləcəyi ən yüksək qiymətdir, çünki $k /15 + 1/30$ k / 15 + 1 / 30 nöqtəsi funksiyanın null nöqtələrindən maksimal məsafədə yerləşir.

Alqoritm yerişinə dair

gcd funksiyası $a$ və $b$ ədədlərinin ən böyük ortaq böləni tapır.

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

lcm funksiyası $a$ və $b$ ədədlərinin ən kiçik ortaq katını tapır.

long long lcm(long long a, long long b)
{
  return a / gcd(a, b) * b;
}

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

while (scanf("%lld %lld", &n, &m) == 2)
{

Cavabı hesablayır və çıxarırıq.

  d = 2 * lcm(n, m);
  printf("%lld/%lld\n", 1, d);
}

f (i, j) = i / n - j / m = \frac{i \cdot m - j \cdot n}{n \cdot m} = \frac{( i \cdot m ) / E B O B ( n , m ) - ( j \cdot n ) / E B O B ( n , m )}{( n \cdot m ) / E B O B ( n , m )} = \frac{i \cdot ( m / E B O B ( n , m )) - j \cdot ( n / E B O B ( n , m ))}{E K Q ( n , m )}

f (t) = mi n_{i, j \in Z} ∣ \frac{i}{n} - \frac{j}{m} + t ∣

f (t) = mi n_{i, j \in Z} ∣ \frac{i}{3} - \frac{j}{5} + t ∣