public class FastMod {
	/**
	 * 计算快速取模的乘法因子
	 *
	 * @param divisor 除数, 有效范围[1,0x7fff_ffff]
	 */
	public static long fastModMultiplier(int divisor) {
		return Long.divideUnsigned(-1, divisor) + 1;
	}

	/**
	 * 无符号快速无符号取模
	 *
	 * @param value 被除数, 有效范围[0,0xffff_ffff]
	 * @param divisor 除数, 有效范围[1,0x7fff_ffff]
	 * @param multiplier 快速取模的乘法因子
	 */
	public static long fastMod(long value, int divisor, long multiplier) {
		return ((((value * multiplier) >>> 32) + 1) * divisor) >>> 32;
	}

	public static void main(String[] args) {
		for (int i = 1; i <= 5; i++) {
			System.out.println(i);
			var c = new FastIntDivCtx(i);
			//noinspection OverflowingLoopIndex
			for (int j = 0; j >= 0; j++) {
				if (c.fastDiv(j) != Integer.divideUnsigned(j, i))
					throw new AssertionError(i + ", " + j);
			}
		}
		System.out.println("OK");
	}

	public static void main1(String[] args) {
		for (int i = 0x1000_0000; i <= 0x1000_0004; i++) {
			System.out.println(i);
			long m = fastModMultiplier(i);
			for (long j = 0; j <= 0xffff_ffffL; j++) {
				if (fastMod(j, i, m) != Long.remainderUnsigned(j, i))
					throw new AssertionError(i + ", " + j);
			}
		}
		System.out.println("OK");
	}

	public static class FastIntDivCtx {
		final int k; // [32,63]
		final long m; // [0,0x1_ffff_fff9]

		// divisor: [1,0x7fff_ffff]
		public FastIntDivCtx(int divisor) {
			k = 64 - Integer.numberOfLeadingZeros(divisor - 1);
			m = Long.divideUnsigned((1L << k) + (divisor - 1), divisor);
		}

		// value/return: [0,0x7fff_ffff]
		public int fastDiv(int value) {
			return (int)((value * m) >>> k);
		}
	}

	public static class FastLongDivCtx {
		final int k; // [0,31]
		final long m; // [0,0xffff_fff9]

		// divisor: [1,0x7fff_ffff]
		public FastLongDivCtx(int divisor) {
			k = 32 - Integer.numberOfLeadingZeros(divisor - 1);
			m = Long.divideUnsigned((1L << (k + 32)) + (divisor - 1), divisor) - 0x1_0000_0000L;
		}

		// value/return: [0,0xffff_ffff]
		public long fastDiv(long value) {
			return (((value * m) >>> 32) + value) >>> k;
		}
	}

	public static class FastDivModCtx {
		private final int shift1; // [0,1]
		private final int shift2; // [0,30]
		private final int divisor; // [1,0x7fff_ffff]
		private final long mul; // [0x1_0000_0001,0x1_ffff_fff9]

		// divisor: [1,0x7fff_ffff]
		public FastDivModCtx(int divisor) {
			if (divisor <= 1)
				throw new IllegalArgumentException();
			shift1 = (divisor & (divisor - 1)) == 0 ? 0 : 1;
			shift2 = 31 - Integer.numberOfLeadingZeros(divisor);
			this.divisor = divisor;
			mul = Long.divideUnsigned(1L << (32 + shift1 + shift2), divisor) + 1;
		}

		// value: [0,0xffff_ffff]
		public long fastDiv(long value) {
			long d = (value * mul) >>> 32;
			value = (value - d) >>> shift1;
			value = (value + d) >>> shift2;
			return value;
		}

		// value: [0,0xffff_ffff]
		public int fastMod(long value) {
			return (int)(value - divisor * fastDiv(value));
		}

		public static class DivMod {
			public long div;
			public int mod;
		}

		// value: [0,0xffff_ffff]
		public void fastDivMod(long value, DivMod divMod) {
			long v = fastDiv(value);
			divMod.div = v;
			divMod.mod = (int)(value - divisor * v);
		}
	}
}