Factovisors

题目描述

分析:若m是合数,把m分解为质因数的乘积
m=(p1^k1)(p2^k2)…(pi^ki)
对于m的每一个质因数pi,若其次数ki都不大于n!里pi的最大次数Ki,则m可以整除n!,反之则不能。
若m是质数,只要m不大于n即可整除n!;若m等于1,m可以整除任何n!。
另外:programming-challenges.com对本答案判定为正确,但UVa却判错。笔者仔细检查了算法和实现,没有发现问题。

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>

using namespace std;

typedef unsigned int uint;
typedef vector<pair<uint, uint> > PVec;

PVec prime_factors(uint m) {
  PVec r;
  uint i = 2;
  uint c = 0;
  while (m % i == 0) {
    m /= i;
    c++;
  }
  if (c)
    r.push_back(make_pair(i, c));
  i = 3;
  while (i <= sqrt(m) + 1) {
    c = 0;
    while (m % i == 0) {
      m /= i;
      c++;
    }
    if (c)
      r.push_back(make_pair(i, c));
    i += 2;
  }
  return r;
}

bool divisible(uint n, uint m) {
  if (m < 2) {
    return m ? true : false;
  }
  bool r = true;
  PVec factors = prime_factors(m);
  if (factors.empty()) {
    if (n < m)
      r = false;
  }
  else {
    for (int i = 0; i < factors.size(); i++) {
      uint p = factors[i].first;
      uint c = factors[i].second;
      uint count = 0;
      uint np;
      uint t = n;
      while ((np = t / p) > 0) {
        count += np;
        if (count >= c)
          break;
        t = np;
      }
      if (count < c) {
        r = false;
        break;
      }
    }
  }
  return r;
}

int main() {
  uint n, m;
  while (cin >> n >> m) {
    if (divisible(n, m)) {
      cout << m << " divides " << n << "!" << endl;
    }
    else {
      cout << m << " does not divide " << n << "!" << endl;
    }
  }
  return 0;
}

《Factovisors》有1个想法

  1. Pingback: 目录 | 狂童

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>