A class providing a fast algorithm for converting a 48 bit structure seed to a nextLong with the same lower 48 bits.

NextLongEquivalentFinder.java

import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class NextLongEquivalentFinder {
    //{0, 107048004364969} offsets
    //{{-33441*2/(32768*2), 46603/65536}, {17549*2/(32768*2), 39761/65536}}/65536 will be our inverse matrix

    /**
     * Adds seeds which give nextLongs congruent to your structure seed to a list.
     * Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
     * @param structureSeed the 48 bit version of the seed
     * @param seedList a list to add the seeds to
     */
    public static void addSeedsToList(long structureSeed, List<Long> seedList) {
        long lowerBits = structureSeed & 0xffff_ffffL;
        long upperBits = structureSeed >>> 32;
        //Did the lower bits affect the upper bits
        if ((lowerBits & 0x8000_0000L) != 0)
            upperBits += 1; //restoring the initial value of the upper bits

        BigDecimal lowMin = BigDecimal.valueOf(lowerBits << 16);
        BigDecimal lowMax = BigDecimal.valueOf(((lowerBits + 1) << 16) - 1);
        //the next two lines seem to only barely require the BigDecimals, so they can probably be avoided if you're careful
        BigDecimal upperMin = BigDecimal.valueOf((upperBits << 16) - 107048004364969L);
        //hardcoded matrix multiplication again
        BigDecimal min1 = lowMax.multiply(BigDecimal.valueOf(-33441*2)).add(upperMin.multiply(BigDecimal.valueOf(17549*2))).divide(BigDecimal.valueOf(1L << 32), RoundingMode.CEILING);
        BigDecimal min2 = lowMin.multiply(BigDecimal.valueOf(46603)).add(upperMin.multiply(BigDecimal.valueOf(39761))).divide(BigDecimal.valueOf(1L << 32), RoundingMode.CEILING);

        long m1lv = min1.longValue();
        long m2lv = min2.longValue();

        //with a lot more effort you can make these loops check 2 things and not 4 but I'm not sure it would even be much faster
        for (int i = 0; i <=1; i++) for (int j = 0; j <=1; j++) {
            long seed = (-39761 * (m1lv + i) + 35098 * (m2lv + j));
            if ((46603 * (m1lv + i) + 66882 * (m2lv + j)) + 107048004364969L >>> 16 == upperBits) {
                if (seed >>> 16 == lowerBits)
                    seedList.add((254681119335897L * seed + 120305458776662L) & 0xffff_ffff_ffffL);
            }
        }
    }

    /**
     * Returns of list of seeds which give nextLongs congruent to your structure seed.
     * Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
     * @param structureSeed the 48 bit version of the seed
     */
    public static ArrayList<Long> getSeeds(long structureSeed) {
        ArrayList<Long> seeds = new ArrayList<>(2);
        addSeedsToList(structureSeed,seeds);
        return seeds;
    }

    /**
     * Adds nextLongs congruent to your structure seed to a list.
     * Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
     * @param structureSeed the 48 bit version of the seed
     * @param nextLongs a list to add the nextLongs to
     */
    public static void addNextLongEquivalents(long structureSeed, List<Long> nextLongs) {
        //this technically does some redundant operations
        for (long seed: getSeeds(structureSeed)) {
            nextLongs.add(new Random(seed ^ 0x5deece66dL).nextLong());
        }
    }

    /**
     * Returns of nextLongs congruent to your structure seed.
     * Has a precondition that structureSeed is 48 bits (its upper 16 bits as a long are 0)
     * @param structureSeed the 48 bit version of the seed
     */
    public static ArrayList<Long> getNextLongEquivalents(long structureSeed) {
        ArrayList<Long> nextLongs = new ArrayList<>(2);
        addNextLongEquivalents(structureSeed,nextLongs);
        return nextLongs;
    }
}