fork(4) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	int n;				//число от которого берется факториал
  6. 	int k;				//число на которое делится факториал числа n
  7.  
  8. 	int primes[37] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157};
  9. 						// ^^^^ массив простых чисел, в идеале должен генерироваться динамически в самом начале - нужны все простые числа не большие k/2
  10. 	int primesCount = 37; //размер массива с простыми числами
  11.  
  12. 	int multK[primesCount];			//массив разложения числа k на простые множители - число в массиве показывает сколько раз встречается в числе k соотвествующее простое число
  13.  
  14. 	int multN[primesCount];			//массив разложения на простые множители числа n! Множители не больше самого большого множителя числа k
  15.  
  16. 	for (int i=0; i<primesCount; i++)
  17. 	{
  18. 		multK[i] = 0;
  19. 		multN[i] = 0;
  20. 	}
  21.  
  22.  
  23. 	cin >> n >> k;
  24.  
  25. 	//раскладываем на простые множители число k
  26. 	int current_prime = 0;		//счетчик индекса простых чисел
  27. 	int temp = k;   //еще не разложеная часть числа k
  28.  
  29. 	while (current_prime<primesCount)
  30. 		if ( temp % primes[current_prime] == 0)
  31. 		{
  32. 			temp/=primes[current_prime];
  33. 			multK[current_prime]++;
  34. 		}
  35. 		else current_prime++;
  36.  
  37.  
  38. 	//раскладываем на простые множители факториал
  39. 	for(int i=2; i<=n; i++)
  40. 	{
  41. 		int current_prime = 0;		//счетчик индекса простых чисел
  42. 		int temp = i;		////еще не разложеная часть факториала
  43.  
  44. 		while (current_prime<primesCount)
  45. 			if (multK[current_prime] > 0)			//пропускаем простые множители которых нет в числе k
  46. 			{
  47. 				if ( temp % primes[current_prime] == 0)
  48. 				{
  49. 					temp/=primes[current_prime];
  50. 					multN[current_prime]++;
  51. 				}
  52. 				else current_prime++;
  53. 			}
  54. 			else current_prime++;
  55. 	}
  56.  
  57.  
  58. 	//находим ответ - минимум от целочисельного деления массива multN на multK
  59. 	int answer = -1;
  60. 	for (int i =0; i<primesCount;i++)
  61. 		{
  62. 			if( multK[i] == 0 ) continue;
  63. 			int temp = multN[i]/multK[i];
  64. 			if (temp<answer || answer == -1) answer = temp;
  65. 		}
  66.  
  67. 	cout << answer;
  68.  
  69. 	return 0;
  70. }
Success #stdin #stdout 0s 3300KB
comments (?)
stdin
copy 
100 100
stdout
copy 
12
https://ideone.com/YKg79Z
language:
C++ (gcc 8.3)
created:
10 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!