Fun puzzle! Here's a C# solution: ` static class NonDivisibleSubsetResult { private class MultiSetModK { private readonly Dictionary Counts; private readonly List distinct; private readonly Dictionary> PartnerDict;

    public MultiSetModK(List<int> source, int k)
    {
        List<int> modded = source.Select(x => x % k).ToList();
        Console.WriteLine("\tAfter modding: " + string.Join(',', modded));
        distinct = modded.Distinct().ToList();
        Counts = distinct.ToDictionary(
            a => a,
            a => modded.Count(b => b == a));

        PartnerDict =
        (from a in distinct
         let partners = new HashSet<int>(
             from b in distinct
             where (a + b) % k == 0
             select b)
         select new { a, partners })
        .ToDictionary(kvp => kvp.a, kvp => kvp.partners);
    }

    public int? MostPartneredElement()
    {
        var result = (from x in distinct
                      let partnerCount = (
                          from y in PartnerDict[x]
                          select y == x ? Counts[y] - 1 : Counts[y]) // Don't count an int as its own partner
                          .Sum()
                      where partnerCount > 0
                      select (x, partnerCount))
               .DefaultIfEmpty((-1, -1))
               .MaxBy(t => t.Item2);

        if (result.Item2 >= 0)
            Console.WriteLine($"{result.Item1} has {result.Item2} partners: {string.Join(',', PartnerDict[result.Item1])}");
        return result.Item2 < 0 ? (int?)null : result.Item1;
    }

    public void RemoveOneOf(int? x)
    {
        if (x == null) return;
        Console.WriteLine("Removing " + x.Value);

        Counts[x.Value] = Counts[x.Value] - 1;

        if (Counts[x.Value] == 0)
        {
            // If none left, purge from the other structures
            distinct.Remove(x.Value);

            foreach (var kvp in PartnerDict)
            {
                if (kvp.Value.Contains(x.Value))
                    kvp.Value.Remove(x.Value);
            }
        }

    }

    public int Count() => Counts.Values.Sum();

}

public static int nonDivisibleSubset(int k, List<int> s)
{
    MultiSetModK modded = new(s, k);

    // Iterate as long as there is an in in the modded list with partners
    for (int? x = modded.MostPartneredElement(); x != null; x = x = modded.MostPartneredElement())
    {
        modded.RemoveOneOf(x);
    }
    return modded.Count();

}

} `