sicily_1009 Mersenne Composite N

题目

Constraints

Time Limit: 1 secs, Memory Limit: 32 MB

Description

One of the world-wide cooperative computing tasks is the "Grand Internet Mersenne Prime Search" -- GIMPS -- striving to find ever-larger prime numbers by examining a particular category of such numbers.
A Mersenne number is defined as a number of the form (2p–1), where p is a prime number -- a number divisible only by one and itself. (A number that can be divided by numbers other than itself and one are called "composite" numbers, and each of these can be uniquely represented by the prime numbers that can be multiplied together to generate the composite number — referred to as its prime factors.)
Initially it looks as though the Mersenne numbers are all primes.

Prime Corresponding Mersenne Number

2 4–1 = 3 -- prime 
3 8–1 = 7 -- prime 
5 32–1 = 31 -- prime 
7 128–1 = 127 -- prime

If, however, we are having a "Grand Internet" search, that must not be the case.
Where k is an input parameter, compute all the Mersenne composite numbers less than 2k -- where k <= 63 (that is, it will fit in a 64-bit signed integer on the computer). In Java, the "long" data type is a signed 64 bit integer. Under gcc and g++ (C and C++ in the programming contest environment), the "long long" data type is a signed 64 bit integer.

Input

Input is from file a. in. It contains a single number, without leading or trailing blanks, giving the value of k. As promised, k <= 63.

Output

One line per Mersenne composite number giving first the prime factors (in increasing order) separate by asterisks, an equal sign, the Mersenne number itself, an equal sign, and then the explicit statement of the Mersenne number, as shown in the sample output. Use exactly this format. Note that all separating white space fields consist of one blank.

Sample Input

Sample Output

23 * 89 = 2047 = ( 2 ^ 11 ) - 1
47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1
233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1

题目大意

找出指数为63或以下的不是素数的梅森数。

思路

有限小个数答案的问题，效率最高的是枚举所有可能的答案，也就是所谓的直接打表。（然而有作弊的嫌疑）
建立好素数表，然后从中筛选。（然而那么大量数据的表，还没建好都TLE了）
简单粗暴地对每个数进行质因数分解。（然而一定会TLE）
只针对符合答案的情况进行计算。（其实这样子和打表没有什么区别）

代码

直接打表版

网上说算到59就够了，是因为$2^{61}-1$是一个梅森素数，这里不用输出。

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// sicily 1009: http://soj.sysu.edu.cn/1009
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int main() {
  int max;
  int answer[9] = { 11, 23, 29, 37, 41, 43, 47, 53, 59 };
  long long int factor[10];
  scanf("%d", &max);

  for (int i = 0; i < 9 && answer[i] <= max; i++) {
    switch (answer[i]) {
      case 11:
        printf("23 * 89 = 2047 = ( 2 ^ 11 ) - 1\n");
        break;
      case 23:
        printf("47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1\n");
        break;
      case 29:
        printf("233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1\n");
        break;
      case 37:
        printf("223 * 616318177 = 137438953471 = ( 2 ^ 37 ) - 1\n");
        break;
      case 41:
        printf("13367 * 164511353 = 2199023255551 = ( 2 ^ 41 ) - 1\n");
        break;
      case 43:
        printf("431 * 9719 * 2099863 = 8796093022207 = ( 2 ^ 43 ) - 1\n");
        break;
      case 47:
        printf("2351 * 4513 * 13264529 = 140737488355327 = ( 2 ^ 47 ) - 1\n");
        break;
      case 53:
        printf("6361 * 69431 * 20394401 = 9007199254740991 = ( 2 ^ 53 ) - 1\n");
        break;
      case 59:
        printf("179951 * 3203431780337 = 576460752303423487 = ( 2 ^ 59 ) - 1\n");
        break;
    }
  }

  return 0;
}

简单粗暴版

大概10s以内的代码, 里面的注释能够帮助理清思路。

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// sicily 1009: http://soj.sysu.edu.cn/1009
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

// get all prime numbers that is no more than num.
// @Param num: the max number that we want the primes less than.
// @return: a prime list.
vector<int> getPrime(int num) {
  vector<int> prime;
  prime.push_back(2);
  for (int i = 3; i <= num; i+=2) {
    bool isPrime = true;
    for (int j = 0; j < prime.size(); j++) {
      if (prime[j] * prime[j] > i) break;
      if (i % prime[j] == 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) prime.push_back(i);
  }

  return prime;
}

int main() {
  // gets all posible exponents.
  vector<int> exponent = getPrime(63);

  int max;
  vector<long long int> factor;
  scanf("%d", &max);

  // exams the corresponding mersenne number for a exponent.
  // if the mersenne is a composite number, outputs it.
  for (int i = 0; i < exponent.size() && exponent[i] <= max; i++) {
    long long int mersenne = (1LL << exponent[i]) - 1;
    long long int temp = mersenne;

    // counts the factors.
    factor.clear();
    for (long long int j = 3; j*j < temp; j += 2) {
      if (temp%j == 0) {
        factor.push_back(j);
        temp /= j;
      }
    }
    // if @temp is less than @mersenne, which means that mersenne has some
    // factors, and temp is also a prime factor for it doesn't divide any
    // numbers less than its square root.
    if (temp < mersenne) factor.push_back(temp);

    // factors exists means mersenne is composite. outputs it.
    if (!factor.empty()) {
      for (int j = 0; j < factor.size(); j++) {
        if (j) printf(" * ");
        printf("%lld", factor[j]);
      }
      printf(" = %lld = ( 2 ^ %d ) - 1\n", mersenne, exponent[i]);
    }
  }

  return 0;
}

优化版

此版本是参考http://www.cnblogs.com/mjc467621163/archive/2011/07/04/2097278.html

只针对符合的结果运算，可能剩下超级多的时间。

// Copyright (c) 2015 HuangJunjie@SYSU(SNO:13331087). All Rights Reserved.
// sicily 1009: http://soj.sysu.edu.cn/1009
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int main() {
  int max;
  int answer[9] = { 11, 23, 29, 37, 41, 43, 47, 53, 59 };
  long long int factor[10];
  scanf("%d", &max);

  for (int i = 0; i < 9 && answer[i] <= max; i++) {
    long long int mersenne = (1LL << answer[i]) - 1;
    long long int temp = mersenne;

    memset(factor, 0, sizeof(factor));
    
    int count = 0;
    for (long long int j = 3; j*j < temp; j+=2) {
      if (temp%j ==0) {
        factor[count++] = j;
        temp /= j;
      }
    }
    if (temp < mersenne) factor[count++] = temp;

    for (int j = 0; j < count; j++) {
      if (j) printf(" * ");
      printf("%lld", factor[j]);
    }
    printf(" = %lld = ( 2 ^ %d ) - 1\n", mersenne, answer[i]);
  }

  return 0;
}

以上两个版本都存在不能检验重复因式的问题，所以对优化版的因子判断（21-28行）进行小改良

    int count = 0;
    for (long long int j = 3; j*j < temp; j += 2) {
      if (temp%j == 0) {
        while (temp%j == 0) {
          factor[count++] = j;
          temp /= j;
        }
      }
    }
    if (temp < mersenne) factor[count++] = temp;

参考

http://m.blog.csdn.net/blog/zhanweeleee/40949933
http://www.cnblogs.com/mjc467621163/archive/2011/07/04/2097278.html

sicily_1009 Mersenne Composite N