fork download
copy 
  1. import java.io.FileNotFoundException;
  2. import java.util.Arrays;
  3.  
  4. public class Main {
  5. 	public static void main(String[] args) throws FileNotFoundException {
  6. 		new Main().run();
  7. 	}
  8.  
  9. 	long pow(long a, long n) {
  10. 		long ret = 1;
  11. 		for (; n > 0; n >>= 1, a = a * a & (MOD - 1)) {
  12. 			if (n % 2 == 1) {
  13. 				ret = ret * a & (MOD - 1);
  14. 			}
  15. 		}
  16. 		return ret;
  17. 	}
  18.  
  19. 	void run() {
  20. 		// a^x = b
  21. 		for (int a = 3; a < MOD; a += 2) {
  22. 			for (int b = 3; b < MOD; b += 2) {
  23. 				int exact = -1;
  24. 				for (int i = 0; i < MOD; ++i) {
  25. 					if (pow(a, i) == b) {
  26. 						exact = i;
  27. 						break;
  28. 					}
  29. 				}
  30. 				long x = Math.max(-1, discretelog(a, b));
  31. 				if (x >= 0) {
  32. 					System.out.println(a + "^" + x + "=" + b + "=" + pow(a, x));
  33. 				}
  34. 				if (x != exact) {
  35. 					throw new AssertionError();
  36. 				}
  37. 			}
  38. 		}
  39. 	}
  40.  
  41. 	final int N = 5;
  42. 	long MOD = 1L << N;
  43.  
  44. 	// a^x = b
  45. 	// x = log_a (b)
  46. 	// x = logb / loga
  47.  
  48. 	// return -1 when fail
  49. 	long discretelog(long a, long b) {
  50. 		if (a % 4 == 1 && b % 4 == 3)
  51. 			return -1;
  52. 		if (b == 1)
  53. 			return 0;
  54. 		if (a == b)
  55. 			return 1;
  56. 		if (a == 1) {
  57. 			return -1;
  58. 		}
  59. 		if (a % 2 == 0 || b % 2 == 0)
  60. 			throw new AssertionError();
  61. 		if (b % 4 == 3) {
  62. 			return 1 + discretelog(a, inv(a, MOD) * b % MOD);
  63. 		}
  64. 		if (a % 4 == 3) {
  65. 			return 2 * discretelog(a * a % MOD, b) % MOD;
  66. 		}
  67. 		long loga = log(a);
  68. 		long logb = log(b);
  69. 		long g = gcd(loga, logb);
  70. 		loga /= g;
  71. 		logb /= g;
  72. 		if (loga % 2 == 0) {
  73. 			return -1;
  74. 		}
  75. 		return logb * inv(loga, MOD) % (1L << (N - Long.numberOfTrailingZeros(a - 1)));
  76. 	}
  77.  
  78. 	long log(long a) {
  79. 		long ret = 0;
  80. 		long x = a - 1;
  81. 		// x^i == 0 (n < 2^i
  82. 		for (int i = 1; i < 2 * N; ++i) {
  83. 			int cnt2 = Long.numberOfTrailingZeros(i);
  84. 			long coe = i >> Long.numberOfTrailingZeros(i);
  85. 			long powx = 1;
  86. 			for (int j = 0; j < i; ++j) {
  87. 				powx = powx * x % MOD;
  88. 				while (cnt2 > 0 && powx % 2 == 0) {
  89. 					powx /= 2;
  90. 					--cnt2;
  91. 				}
  92. 			}
  93. 			ret += (i % 2 == 0 ? MOD - 1 : 1) * powx % MOD * inv(coe, MOD) % MOD;
  94. 			ret %= MOD;
  95. 		}
  96. 		return ret;
  97. 	}
  98.  
  99. 	// inv[0] := 1
  100. 	public long inv(long a, long mod) {
  101. 		a %= mod;
  102. 		if (gcd(a, mod) != 1)
  103. 			throw new AssertionError();
  104. 		if (a < 0)
  105. 			a += mod;
  106. 		if (a == 0)
  107. 			return 1;
  108. 		long b = mod;
  109. 		long p = 1, q = 0;
  110. 		while (b > 0) {
  111. 			long c = a / b;
  112. 			long d;
  113. 			d = a;
  114. 			a = b;
  115. 			b = d % b;
  116. 			d = p;
  117. 			p = q;
  118. 			q = d - c * q;
  119. 		}
  120. 		return p < 0 ? p + mod : p;
  121. 	}
  122.  
  123. 	long gcd(long a, long b) {
  124. 		if (a < b) {
  125. 			a ^= b;
  126. 			b ^= a;
  127. 			a ^= b;
  128. 		}
  129. 		if (b == 0) {
  130. 			return a;
  131. 		}
  132. 		return gcd(a % b, b);
  133. 	}
  134.  
  135. 	static void tr(Object... objects) {
  136. 		System.out.println(Arrays.deepToString(objects));
  137. 	}
  138. }
  139.  
Success #stdin #stdout 0.14s 36976KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3^1=3=3
3^2=9=9
3^7=11=11
3^4=17=17
3^5=19=19
3^6=25=25
3^3=27=27
5^1=5=5
5^6=9=9
5^7=13=13
5^4=17=17
5^5=21=21
5^2=25=25
5^3=29=29
7^1=7=7
7^2=17=17
7^3=23=23
9^1=9=9
9^2=17=17
9^3=25=25
11^7=3=3
11^6=9=9
11^1=11=11
11^4=17=17
11^3=19=19
11^2=25=25
11^5=27=27
13^7=5=5
13^2=9=9
13^1=13=13
13^4=17=17
13^3=21=21
13^6=25=25
13^5=29=29
15^1=15=15
17^1=17=17
19^5=3=3
19^2=9=9
19^3=11=11
19^4=17=17
19^1=19=19
19^6=25=25
19^7=27=27
21^5=5=5
21^6=9=9
21^3=13=13
21^4=17=17
21^1=21=21
21^2=25=25
21^7=29=29
23^3=7=7
23^2=17=17
23^1=23=23
25^3=9=9
25^2=17=17
25^1=25=25
27^3=3=3
27^6=9=9
27^5=11=11
27^4=17=17
27^7=19=19
27^2=25=25
27^1=27=27
29^3=5=5
29^2=9=9
29^5=13=13
29^4=17=17
29^7=21=21
29^6=25=25
29^1=29=29
31^1=31=31
https://ideone.com/F0SOp3
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!