Guest User

Untitled

a guest
Jun 18th, 2018
322
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.64 KB | None | 0 0
  1. import static java.util.stream.Collectors.summingInt;
  2.  
  3. import java.io.BufferedOutputStream;
  4. import java.io.BufferedReader;
  5. import java.io.IOException;
  6. import java.io.InputStreamReader;
  7. import java.io.PrintWriter;
  8. import java.util.ArrayList;
  9. import java.util.HashSet;
  10. import java.util.List;
  11. import java.util.Map;
  12. import java.util.Set;
  13. import java.util.StringTokenizer;
  14. import java.util.function.Function;
  15. import java.util.stream.Collectors;
  16.  
  17. public class Template {
  18. static List<Integer>[] gr;
  19.  
  20. static long[] arr;
  21. static long n, m, p, q, k, ans;
  22. static boolean b;
  23. static String s, big;
  24.  
  25. public static Map<Long, Integer> factorize(long n) {
  26. List<Long> factors = new ArrayList<>();
  27. for (long d = 2; d * d <= n; d++) {
  28. while (n % d == 0) {
  29. factors.add(d);
  30. n /= d;
  31. }
  32. }
  33. if (n > 1) {
  34. factors.add(n);
  35. }
  36. return factors.stream().collect(Collectors.groupingBy(Function.identity(), summingInt(v -> 1)));
  37. }
  38.  
  39. static long ANS = 0;
  40. static Set<Long> pairs = new HashSet<>();
  41.  
  42. static void rec(long a, long b, int idx, List<Long> set) {
  43. if (idx == set.size()) {
  44. if (a >= l && b >= l && b <= r && a <= r) {
  45. if (a == b) {
  46. if (pairs.add(a)) {
  47. ANS++;
  48. }
  49. } else
  50. ANS++;
  51. }
  52. return;
  53. }
  54. rec(a * set.get(idx), b, idx + 1, set);
  55. rec(a, b * set.get(idx), idx + 1, set);
  56. }
  57.  
  58. static int l, r;
  59.  
  60. public static void main(String[] args) {
  61. l = in.nextInt();
  62. r = in.nextInt();
  63. int x = in.nextInt();
  64. int y = in.nextInt();
  65.  
  66. int xx = y / x;
  67. if (y % x != 0) {
  68. System.out.println(0);
  69. return;
  70. }
  71. Map<Long, Integer> map = factorize(xx);
  72. List<Long> list = new ArrayList<>();
  73. for (java.util.Map.Entry<Long, Integer> e : map.entrySet()) {
  74. long pow = 1;
  75. for (int i = 0; i < e.getValue(); i++) {
  76. pow *= e.getKey();
  77. }
  78. list.add(pow);
  79. }
  80. rec(1, 1, 0, list);
  81. System.out.println(ANS);
  82. out.close();
  83. }
  84.  
  85. static MyScanner in = new MyScanner();
  86. static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  87.  
  88. static boolean valid(int[][] arr, int x, int y) {
  89. return x >= 0 && y >= 0 && x < arr.length && y < arr[0].length;
  90. }
  91.  
  92. static int[] d1 = { -1, -1, -1, 1, 1, 1, 0, 0 };
  93. static int[] d2 = { 1, 0, -1, 0, -1, 1, -1, 1 };
  94.  
  95. static int DIRECTED = 1, UNDIRECTED = 0;
  96.  
  97. static void dfsTree(int root, int parent) {
  98. for (int child : gr[root]) {
  99. if (child == parent) {
  100. continue;
  101. }
  102. dfsTree(child, root);
  103. }
  104. }
  105.  
  106. static List<Integer>[] readGraph(int dir, int n) {
  107. List<Integer>[] gr;
  108. gr = new ArrayList[(int) (n + 1)];
  109. for (int i = 1; i <= n; i++) {
  110. gr[i] = new ArrayList();
  111. }
  112. for (int i = 1; i < n; i++) {
  113. int u = in.nextInt(), v = in.nextInt();
  114. gr[v].add(u);
  115. if (dir == UNDIRECTED) {
  116. gr[u].add(v);
  117. }
  118. }
  119. return gr;
  120. }
  121.  
  122. public static long gcd(long a, long b) {
  123. while (b != 0) {
  124. long t = b;
  125. b = a % b;
  126. a = t;
  127. }
  128. return Math.abs(a);
  129. }
  130.  
  131. public static long lcm(long a, long b) {
  132. return Math.abs(a / gcd(a, b) * b);
  133. }
  134.  
  135. // gcd(a, b) = x, lcm(a,b) = y
  136. /*
  137. *
  138. * a*b/x = y a*b = x*y
  139. *
  140. *
  141. */
  142. static class Pair implements Comparable<Pair> {
  143. long a, b;
  144.  
  145. public Pair(long a, long b) {
  146. this.a = a;
  147. this.b = b;
  148. }
  149.  
  150. @Override
  151. public int compareTo(Pair p) {
  152. return a == p.a ? 0 : (a > p.a ? 1 : -1);
  153. }
  154.  
  155. @Override
  156. public int hashCode() {
  157. final int prime = 31;
  158. int result = 1;
  159. result = prime * result + (int) (a ^ (a >>> 32));
  160. result = prime * result + (int) (b ^ (b >>> 32));
  161. return result;
  162. }
  163.  
  164. @Override
  165. public boolean equals(Object obj) {
  166. if (this == obj)
  167. return true;
  168. if (obj == null)
  169. return false;
  170. if (getClass() != obj.getClass())
  171. return false;
  172. Pair other = (Pair) obj;
  173. if (a != other.a)
  174. return false;
  175. if (b != other.b)
  176. return false;
  177. return true;
  178. }
  179. }
  180.  
  181. public static class MyScanner {
  182. BufferedReader br;
  183. StringTokenizer st;
  184.  
  185. public MyScanner() {
  186. br = new BufferedReader(new InputStreamReader(System.in));
  187. }
  188.  
  189. String next() {
  190. while (st == null || !st.hasMoreElements()) {
  191. try {
  192. st = new StringTokenizer(br.readLine());
  193. } catch (IOException e) {
  194. e.printStackTrace();
  195. }
  196. }
  197. return st.nextToken();
  198. }
  199.  
  200. int nextInt() {
  201. return Integer.parseInt(next());
  202. }
  203.  
  204. long nextLong() {
  205. return Long.parseLong(next());
  206. }
  207.  
  208. double nextDouble() {
  209. return Double.parseDouble(next());
  210. }
  211.  
  212. String nextLine() {
  213. String str = "";
  214. try {
  215. str = br.readLine();
  216. } catch (IOException e) {
  217. e.printStackTrace();
  218. }
  219. return str;
  220. }
  221. }
  222. }
Advertisement
Add Comment
Please, Sign In to add comment