fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. // Function to check if it's possible for a prime factor to divide n! the required number of times
  6. bool solve(int n, int p, int reqCount) {
  7.     long long pv = p;
  8.  
  9.     // Iteratively calculate the sum of quotients n / (prime ^ i) until n / (prime ^ i) becomes zero or reqCount reaches zero
  10.     while (n / pv && reqCount > 0) {
  11.         reqCount -= n / pv;
  12.         pv *= p;
  13.     }
  14.  
  15.     // If the reqCount becomes non-positive, return true, indicating that the prime factor can divide n!
  16.     return reqCount <= 0;
  17. }
  18.  
  19. int main() {
  20.     int n, d, c, t;
  21.     bool isDiv;
  22.  
  23.     // Reading input until end of file
  24.     while (cin >> n >> d) {
  25.         t = d;
  26.         isDiv = true;
  27.  
  28.         // Iterate through all prime
  29.         for (int i = 2; i * i <= d && isDiv; ++i) {
  30.             c = 0;
  31.  
  32.             // Count the number of times i divides d
  33.             while (d % i == 0) {
  34.                 d /= i;
  35.                 ++c;
  36.             }
  37.  
  38.             // If i divides d at least once, check if it's possible for i to divide n!
  39.             if (c > 0)
  40.                 isDiv = solve(n, i, c);
  41.         }
  42.  
  43.         // If d is still greater than 1 and isDiv is true, check if it's possible for d to divide n!
  44.         if (d > 1 && isDiv) {
  45.             isDiv = solve(n, d, 1);
  46.         }
  47.  
  48.         // Print the result indicating whether d divides n! or not using if-else
  49.         if (isDiv) {
  50.             cout << t << " divides " << n << "!\n";
  51.         } else {
  52.             cout << t << " does not divide " << n << "!\n";
  53.         }
  54.     }
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.01s 5264KB
comments (?)
stdin
copy 
6 9
6 27
20 10000
20 100000
1000 1009
stdout
copy 
9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!
https://ideone.com/ajnIxP
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!