fork download
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.  
  11.  
  12. private static long solve1(long n, long m, long a, long d) {
  13. long[] ar = new long[5];
  14.  
  15. ar[0] = a;
  16. ar[1] = a + d;
  17. ar[2] = a + 2 * d;
  18. ar[3] = a + 3 * d;
  19. ar[4] = a + 4 * d;
  20.  
  21. long count = 0;
  22.  
  23. for (byte i = 0 ; i < 2 ; i++) {
  24. for (byte j = 0; j < 2; j++) {
  25. for (byte k = 0; k < 2; k++) {
  26. for (byte l = 0; l < 2; l++) {
  27. for (byte o = 0; o < 2; o++) {
  28. long divisible = 1;
  29. int eleCount = 0;
  30.  
  31. if (i == 1) {
  32. divisible *= ar[0];
  33. eleCount++;
  34. }
  35.  
  36. if (j == 1) {
  37. divisible = lcm(divisible, ar[1]);
  38. eleCount++;
  39. }
  40.  
  41.  
  42. if (k == 1) {
  43. divisible = lcm(divisible, ar[2]);
  44. eleCount++;
  45. }
  46.  
  47. if (l == 1) {
  48. divisible = lcm(divisible, ar[3]);
  49. eleCount++;
  50. }
  51.  
  52. if (o == 1) {
  53. divisible = lcm(divisible, ar[4]);
  54. eleCount++;
  55. }
  56.  
  57. if (eleCount == 0) {
  58. continue;
  59. }
  60.  
  61. int sign = eleCount % 2 == 0 ? -1 : 1;
  62. count += sign * getDivCount(n, m, divisible);
  63. }
  64. }
  65. }
  66. }
  67. }
  68.  
  69. return m - n + 1 - count;
  70. }
  71.  
  72. private static long getDivCount(long n, long m, long x) {
  73. return (m / x) + 1 - ((n + x - 1) / x);
  74. }
  75.  
  76. static long gcd(long a, long b){
  77. if (a == 0) return b;
  78.  
  79. return gcd(b %a, a);
  80. }
  81.  
  82. static long lcm(long a, long b){
  83. if (a < b)
  84. return (a*b) / gcd(a, b);
  85.  
  86. return (a*b) / gcd(b, a);
  87. }
  88.  
  89. public static void main (String[] args) throws java.lang.Exception
  90. {
  91. Scanner sc = new Scanner(System.in);
  92. int t = sc.nextInt();
  93. for(int i=0;i<t;++i)
  94. {
  95. long n,m,a,d;
  96. n = sc.nextLong();
  97. m = sc.nextLong();
  98. a = sc.nextLong();
  99. d = sc.nextLong();
  100. System.out.println(solve1(n,m,a,d));
  101. }
  102. }
  103.  
  104.  
  105. }
  106.  
Success #stdin #stdout 0.07s 2184192KB
stdin
5
2 100 3347826 4238924560
427857 3478462350 8 3947823956
5 73 64567 8
4 35 36 7
3 65 10 127
stdout
100
3043280184
73
32
57