fork download
copy 
  1. #include <iostream>
  2. #include <map>
  3.  
  4. using namespace std;
  5.  
  6. // Function to calculate the factorial of a number
  7. unsigned long long factorial(int n) {
  8.     if (n == 0 || n == 1)
  9.         return 1;
  10.     else
  11.         return n * factorial(n - 1);
  12. }
  13.  
  14. int main() {
  15.     int n, m;
  16.  
  17.     // Reading input until EOF (End of File)
  18.     while (cin >> n >> m) {
  19.         // Check if m is greater than n
  20.         if (m > n) {
  21.             cout << m << " does not divide " << n << "!\n";
  22.             continue;
  23.         }
  24.  
  25.         // Calculate factorial of n
  26.         unsigned long long factN = factorial(n);
  27.  
  28.         // Map to store prime factors of m and their counts
  29.         map<int, int> primeFactorsM;
  30.  
  31.         // Factorize m
  32.         int tempM = m;
  33.         for (int i = 2; i * i <= tempM; ++i) {
  34.             while (tempM % i == 0) {
  35.                 primeFactorsM[i]++;
  36.                 tempM /= i;
  37.             }
  38.         }
  39.         if (tempM > 1) {
  40.             primeFactorsM[tempM]++;
  41.         }
  42.  
  43.         // Check divisibility of m in n!
  44.         bool divides = true;
  45.         for (auto& factor : primeFactorsM) {
  46.             int prime = factor.first;
  47.             int count = factor.second;
  48.  
  49.             // Calculate the power of prime in n!
  50.             unsigned long long temp = prime;
  51.             unsigned long long powerCount = 0;
  52.             while (temp <= n) {
  53.                 powerCount += n / temp;
  54.                 temp *= prime;
  55.             }
  56.  
  57.             // If the power of prime in n! is less than count in m, m doesn't divide n!
  58.             if (powerCount < count) {
  59.                 divides = false;
  60.                 break;
  61.             }
  62.         }
  63.  
  64.         // Output result
  65.         if (divides) {
  66.             cout << m << " divides " << n << "!\n";
  67.         } else {
  68.             cout << m << " does not divide " << n << "!\n";
  69.         }
  70.     }
  71.  
  72.     return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
6 9
6 27
20 10000
20 100000
1000 1009
stdout
copy 
9 does not divide 6!
27 does not divide 6!
10000 does not divide 20!
100000 does not divide 20!
1009 does not divide 1000!
https://ideone.com/IK4HOR
problem BIT2, based on SPOJ submission 11034498 (C++ 4.3.2), 2014-02-09 15:54:15
language:
C++ (gcc 8.3)
created:
17 days 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!