更多PAT題解盡在我的個人博客---我的個人bok

題目

OJ平臺

題目翻譯

題目描述

原文
Among all the factors of a positive integer N, there may exist several consecutive numbers. For example, 630 can be factored as 3 * 5 * 6 * 7, where 5, 6, and 7 are the three consecutive numbers. Now given any positive N, you are supposed to find the maximum number of consecutive factors, and list the smallest sequence of the consecutive factors.
翻譯
在正數(shù)N的所有因數(shù)中，可能存在一些連續(xù)的數(shù)字。舉個例子，630 可以 被 3*5*6*7 組成，這里的 5*6*7 是三個連續(xù)的數(shù)字?，F(xiàn)在給定任意一個正數(shù)N，你應(yīng)該找出最大的連續(xù)因子數(shù)量，并且列出最小的連續(xù)因子序列。

題目解析

很簡單，直接暴力：
解題思路：外層遍歷起點，里層遍歷連續(xù)的因子，最后取最長的結(jié)果即可。

代碼拆解

1. Input()函數(shù)輸入和更新

   void Input() {
   ios::sync_with_stdio(false);
   cin >> N;
   int cmp = sqrt(N);
   for (int i = 2; i <= cmp; i++) {
    int t = N, start = i;
    while (t % start == 0) { //一旦出現(xiàn)不連續(xù)的情況直接跳出循環(huán)
      t /= start;
      start++;
    }
    if (start - i > mxLen) {//開始更新
      mxLen = start - i;
      first = i;
    }
   }
   }

2. print函數(shù)輸出結(jié)果

   void print() {
   if (mxLen) { //一旦能分解成多個就這樣打印，否則就是沒有更新，則輸出1
    cout << mxLen << endl;
    cout << first;
    for (int i = 1; i < mxLen; i++) {
      cout << '*' << first + i;
    }
   }
   else {
    cout << 1 << endl;
    cout << N;
   }
   }

   整合代碼得出答案

   效率還行

   

#include<bits/stdc++.h>
using namespace std;
int N, first, mxLen; //數(shù)字，起點，最大的長度
//解題思路：外層遍歷起點，里層遍歷連續(xù)的因子，最后取最長的結(jié)果即可。
void Input() {
  ios::sync_with_stdio(false);
  cin >> N;
  int cmp = sqrt(N);
  for (int i = 2; i <= cmp; i++) {
    int t = N, start = i;
    while (t % start == 0) { //一旦出現(xiàn)不連續(xù)的情況直接跳出循環(huán)
      t /= start;
      start++;
    }
    if (start - i > mxLen) {
      mxLen = start - i;
      first = i;
    }
  }
}
void print() {
  if (mxLen) { //一旦能分解成多個就這樣打印，否則就是沒有更新，則輸出1
    cout << mxLen << endl;
    cout << first;
    for (int i = 1; i < mxLen; i++) {
      cout << '*' << first + i;
    }
  }
  else {
    cout << 1 << endl;
    cout << N;
  }

}
int main() {
  Input();
  print();
  return 0;
}