fork(2) download
copy 
  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
comments (?)
stdin
copy 
5
2 100 3347826 4238924560
427857 3478462350 8 3947823956
5 73 64567 8
4 35 36 7
3 65 10 127
stdout
copy 
100
3043280184
73
32
57
https://ideone.com/IphpVx
language:
Java (HotSpot 12)
created:
5 years ago
visibility:
public

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!