using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    public static void Main()

    {

        long p = 709;

        long q = 433;

        long phi = (p - 1) * (q - 1);

        Console.WriteLine($"ф(n): {phi}\n");

        Dictionary<(long, long), int> distribution = new();

        for (long e = 3; e < phi; e++)

        {

            long d, _;

            if (GCD(e, phi, out d, out _) != 1) continue;

            d = (d + phi) % phi;

            // quot - делитель e на d, rem - остаток от деления

            long quot = Math.DivRem(e, d, out long rem);

            if (!distribution.ContainsKey((quot, rem)))

                distribution[(quot, rem)] = 0;

            distribution[(quot, rem)] += 1;

            // Выводит пары e и d, для которых e / d = 1 с остатком 168

            //if (quot == 1 && rem == 168)

            //  Console.WriteLine((e, d));

        }

​

        var sorted = from entry in distribution orderby entry.Value descending select entry;

        foreach (var kvp in sorted)

        {

            // Выводит соответственно делитель quot, остаток rem и количество пар e, d,

            // для которых e = quot * d + rem, в порядке убывания последнего

            Console.WriteLine((kvp.Key.Item1, kvp.Key.Item2, kvp.Value));

        }

    }

    // n*x + m*y = gcd(n, m);

    public static long GCD(long n, long m, out long x, out long y)

    {

        long x0 = 1, x1 = 0;

        long y0 = 0, y1 = 1;

        while (m != 0)

        {

            long q, r;

            q = Math.DivRem(n, m, out r);

            n = m;

            m = r;

            long x2 = x0 - q * x1;

            x0 = x1;

            x1 = x2;

            long y2 = y0 - q * y1;

            y0 = y1;

            y1 = y2;

        }

        x = x0;

        y = y0;

        return n;

    }

}

​