fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. int hexDigitToVal(char hex_digit) {
  12. 	if ('0' <= hex_digit && hex_digit <= '9') return (hex_digit - '0');
  13. 	hex_digit = toupper(hex_digit); 
  14. 	return 10 + (hex_digit - 'A');  
  15. }
  16.  
  17. char valToHexDigit(int val) {
  18. 	if (val <= 9) return '0' + val;  
  19. 	return 'A' + (val - 10); 
  20. }
  21.  
  22. struct BigInt {	
  23. 	static const int BASE = 16;  
  24.  
  25. 	vector<int> a; 
  26.  
  27. 	BigInt() {}
  28.  
  29. 	BigInt(ll x) {
  30. 		for (; x > 0; x /= BASE) {
  31. 			a.push_back(x % BASE); 
  32. 		}
  33. 	}
  34.  
  35. 	BigInt(const string &s) {
  36. 		for (int i = 0; i < s.size(); i++){
  37. 			a.push_back(hexDigitToVal(s[i])); 
  38. 		}
  39. 		reverse(a.begin(), a.end()); 
  40. 		trim();
  41. 	}
  42.  
  43. 	void trim() {
  44. 		while (!a.empty() && a.back() == 0) {
  45. 			a.pop_back(); 
  46. 		}
  47. 	}
  48.  
  49. 	bool isZero() {
  50. 		return (a.empty()); 
  51. 	}
  52.  
  53. 	BigInt operator+=(const BigInt &other) {
  54. 		int n = a.size(), m = other.a.size(); 
  55. 		int carry = 0; 
  56. 		for (int i = 0; i < max(n, m) || carry; i++) {
  57. 			if (i == a.size()) {
  58. 				a.push_back(0); 
  59. 			}
  60. 			a[i] += (i < m ? other.a[i] : 0) + carry; 
  61. 			carry = (a[i] >= BASE);   
  62. 			if (carry) a[i] -= BASE;   
  63. 		}	
  64. 		return *this; 
  65. 	}
  66.  
  67. 	BigInt operator-=(const BigInt &other) {
  68. 		int m = other.a.size(); 
  69. 		int carry = 0;  
  70. 		for (int i = 0; i < m || carry; i++) {
  71. 			a[i] -= (i < m ? other.a[i] : 0) + carry; 
  72. 			carry = (a[i] < 0); 
  73. 			if (carry) a[i] += BASE;  
  74. 		}
  75. 		trim();
  76. 		return *this; 
  77. 	}
  78.  
  79. 	BigInt operator+(const BigInt &other) const {
  80. 		return BigInt(*this) += other; 
  81. 	}
  82.  
  83. 	BigInt operator-(const BigInt &other) const { 
  84. 		return BigInt(*this) -= other; 
  85. 	}
  86.  
  87. 	int operator%(int b) const {
  88. 		int n = a.size(); 
  89. 		int carry = 0;  
  90. 		for (int i = n - 1; i >= 0; i--) {
  91. 			ll cur = a[i] + 1ll * carry * BASE;  
  92. 			carry = cur % b; 
  93. 		}
  94. 		return carry;  
  95. 	}
  96.  
  97. 	bool operator<(const BigInt &other) const {
  98. 		int n = a.size(), m = other.a.size(); 
  99. 		if (n != m) {
  100. 			return (n < m); 
  101. 		}
  102. 		for (int i = n - 1; i >= 0; i--) {
  103. 			if (a[i] != other.a[i]) {
  104. 				return (a[i] < other.a[i]); 
  105. 			}
  106. 		}
  107. 		return false; 
  108. 	}
  109.  
  110. 	bool operator>(const BigInt &other) const {
  111. 		return (other < *this); 
  112. 	}
  113.  
  114. 	bool operator<=(const BigInt &other) const {
  115. 		return !(other < *this);
  116. 	}
  117.  
  118. 	bool operator>=(const BigInt &other) const {
  119. 		return !(*this < other); 
  120. 	}
  121.  
  122. 	friend istream& operator>>(istream &in, BigInt &num) {
  123. 		string s;
  124. 		in >> s; 	
  125. 		num = BigInt(s);  
  126. 		return in; 
  127. 	}
  128.  
  129. 	friend ostream& operator<<(ostream &out, const BigInt &num) {
  130. 		out << (num.a.empty() ? 0 : valToHexDigit(num.a.back())); 
  131. 		for (int i = (int)num.a.size() - 2; i >= 0; i--) {
  132. 			out << valToHexDigit(num.a[i]);  
  133. 		}
  134. 		return out; 
  135. 	}
  136. }; 
  137.  
  138. // Tính chất cơ bản của đồng dư cần biết trong bài này:
  139. // (a + b) % c = (a % c + b % c) % c
  140. // (a * b) % c = ((a % c) * (b % c)) % c
  141.  
  142. // Bài toán digital root: 
  143. // Xét BASE bất kì và một số nguyên dương n được biểu diễn ở hệ cơ số BASE
  144. // thực hiện gán n = s(n) cho đến khi n < BASE 
  145. // Ta chứng minh được n = s(n) (mod (BASE - 1))
  146. // Và từ đây ta suy ra được n = s(n) = s(s(n)) = ... = s(s(s(...))) (mod (BASE - 1))
  147. // Nên đáp án của bài toán chính là r = n % (BASE - 1), trường hợp r = 0 thì kết quả là BASE
  148.  
  149. // Áp dụng vào bài này (với BASE = 16) thì ta cần đi tính r = n % 15 = [x * (x + 1) * ... * (y - 1) * y] % 15
  150. //                                                   = [x % 15 * (x + 1) % 15 * ... * (y - 1) % 15 * y % 15] % 15
  151. // Nhận xét:
  152. // - Nếu y - x + 1 >= 15 thì chắc chắn tồn tại một số chia hết cho 15, do đó r = 0 
  153. // Như vậy chỉ còn trường hợp y - x + 1 < 15: 
  154. // - Đến đây có thể code thêm operator% một số BigInt với một số nhỏ.
  155. // - Hoặc dùng tính chất x = s(x) (mod 15), tức tính tổng các chữ số của x trước (để lưu được trong biến int), rồi mới % 15.
  156.  
  157. int main() {
  158. 	ios::sync_with_stdio(false); 
  159. 	cin.tie(nullptr);
  160. 	BigInt x, y; 
  161. 	cin >> x;  
  162. 	cin >> y;  
  163.  
  164. 	if (y - x >= 14) {
  165. 		cout << 'F' << '\n'; 
  166. 		return 0; 
  167. 	}
  168.  
  169. 	int r = 1; 
  170. 	for (BigInt i = x; i <= y; i = i + 1) {
  171. 		r = r * (i % 15) % 15; 
  172. 	}
  173.  
  174. 	cout << (r == 0 ? 'F' : valToHexDigit(r)) << '\n'; 
  175. }
  176.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
1Ba
1Bd
stdout
copy 
F
https://ideone.com/OuX9rR
language:
C++14 (gcc 8.3)
created:
192 days 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!