PAT-L1-006. 連續因子（思維）

L1-006. 連續因子

時間限制

400 ms

記憶體限制

65536 kB

代碼長度限制

8000 B

判題程式

Standard

作者

陳越

一個正整數N的因子中可能存在若幹連續的數字。例如630可以分解為3*5*6*7，其中5、6、7就是3個連續的數字。給定任一正整數N，要求編寫程式求出最長連續因子的個數，并輸出最小的連續因子序列。

輸入格式：

輸入在一行中給出一個正整數N（1< N< 231）。

輸出格式：

首先在第1行輸出最長連續因子的個數；然後在第2行中按“因子1 * 因子2 * …… * 因子k ”的格式輸出最小的連續因子序列，其中因子按遞增順序輸出，1不算在内。

輸入樣例：

630

輸出樣例：

3

5*6*7

非常有意思的題目;

題目讓找出len個連續的數字相乘是n的約數。根據n的範圍，我們可知道，len的長度至多為12，因為（13!)>2^31;

是以，我們從最長的情況開始暴力。當len個連續數字相乘是n的約數的話，就說明找到了正确答案。當循環結束之後仍未找到，說明n是個質數。特判一下。

#include<bits/stdc++.h>
using namespace std;

const int MAX = +;
const int INF = ;


int main(){
    int n;
    scanf("%d",&n);
    int flag=;
    for(int len=;len>=;len--){//len個連續數字相成
        int start = ;//起始數字為2
        for(int j = start;j<=sqrt(n);j++){//其實數字從2--sqrt（n），的各種情況
            int temp=;
            for(int k = ;k<len;k++){
                temp*=(j+k);
            }
            if(n%temp==){//如果乘積是n的約數，說明找到了答案，輸出。
                flag=;
                printf("%d\n",len);
                for(int s = j;s<j+len-;s++){
                    printf("%d*",s);
                }
                printf("%d\n",j+len-);
                return ;//找到了，是以跳出
            }
        }
    }
    if(flag==){//沒有找到，說明n是一個質數，輸出1\n1
        printf("%d\n%d",,n);
    }
    return ;
}