fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #define Compute_prime 100000
  5. using namespace std;
  6.  
  7. bool* PrimeArray;
  8.  
  9. void swap(vector< long long> &arr,int i, int j)
  10. {
  11. 	int temp;
  12. 	if (i != j)
  13. 	{
  14. 		temp = arr[i];
  15. 		arr[i] = arr[j];
  16. 		arr[j] = temp;
  17. 	}
  18. }
  19.  
  20. void Permutation(vector< long long> &arr, vector< long long> &arr2,int n, int r, int depth) //Permutation(N,R,0); NcR
  21. {
  22. 	int i;
  23. 	 long long mid_value=1;
  24. 	if (n == r)
  25. 	{
  26. 		for (i = 0; i<r; i++) {
  27. 			mid_value *= arr[i];
  28. 		}
  29. 		arr2.push_back(mid_value);
  30. 		return;
  31. 	}
  32. 	if (r == depth) {
  33. 		for (i = 0; i<r; i++) {
  34. 			mid_value *= arr[i];
  35. 		}
  36. 		arr2.push_back(mid_value);
  37. 	}
  38.  
  39. 	for (i = depth; i<n; i++) {
  40. 		swap(arr,i, depth);
  41. 		Permutation(arr,arr2,n, r, depth + 1);
  42. 		swap(arr,i, depth);
  43. 	}
  44. }
  45.  
  46.  
  47. long long numberOfMultuples( long long A,  long long B,  long long n)
  48. {
  49. 	if (n == 1)
  50. 		return B + 1 - A;
  51. 	else if (A%n == 0)
  52. 		return (B / n) - (A / n)+1;
  53. 	else
  54. 		return (B / n) - (A / n);
  55. }
  56.  
  57. void Eratos(int n)
  58. {
  59. 	if (n <= 1) return;
  60.  
  61.  
  62. 	for (int i = 2; (i*i) <= n; i++)
  63. 	{
  64. 		if (PrimeArray[i])
  65. 		{
  66. 			for (int j = i*i; j <= n; j += i) PrimeArray[j] = false;
  67. 		}
  68. 	}
  69. }
  70.  
  71. void Factorization(vector< long long> &arr,  long long N)
  72. {
  73. 	for (long long i = 2; i <= N; i++)
  74. 		if (i<Compute_prime && PrimeArray[i] && N%i == 0 )
  75. 		{
  76. 			arr.push_back(i);
  77. 			while(N%i==0) N /= i;
  78. 		}
  79. 		else if (i >= Compute_prime-2)
  80. 		{
  81. 			arr.push_back(N);
  82. 			break;
  83. 		}
  84. }
  85.  
  86. int main()
  87. {
  88. 	int T;
  89.  
  90. 	scanf("%d", &T);
  91.  
  92. 	PrimeArray = new bool[Compute_prime+1];
  93. 	Eratos(Compute_prime);
  94.  
  95. 	for (int j = 0; j<T; j++)
  96. 	{
  97. 		 long long A, B, N, sum = 0;
  98. 		cin >> A >> B >> N;
  99.  
  100. 		vector< long long> arr;
  101.  
  102. 		Factorization(arr, N);
  103.  
  104. 		sum = B + 1 - A;
  105. 		for (int i = 1; i <= arr.size(); i++) //i가 1일때는 arr.size() C 1
  106. 		{
  107. 			vector< long long> arr2;
  108. 			Permutation(arr, arr2, arr.size(), i, 0);
  109. 			sort(arr2.begin(), arr2.end());
  110. 			arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());
  111. 			if (i % 2 == 1) // -차례
  112. 			{		
  113. 				for (int j = 0; j < arr2.size(); j++)
  114. 					sum -= numberOfMultuples(A, B, arr2[j]);
  115.  
  116. 			}
  117. 			else // +차례
  118. 			{
  119. 				for (int j = 0; j < arr2.size(); j++)
  120. 					sum += numberOfMultuples(A, B, arr2[j]);
  121. 			}
  122. 		}
  123.  
  124. 		printf("Case #%d: %lld\n", j + 1, sum);
  125. 	}
  126. }
Success #stdin #stdout 0s 16056KB
comments (?)
stdin
copy 
2
1 10 2
3 15 5
stdout
copy 
Case #1: 10
Case #2: 13
https://ideone.com/pVw0LF
language:
C++14 (gcc 8.3)
created:
6 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!