001 F - lim Divided

2 secs 1024 MB
Daigakuimokempi's icon Daigakuimokempi
Tweet
問題
提出
テストケース
解説

NN を 22 からどんどん割れるか試し、 割れたら記録し、 M−1M-1 個因数が出たら残った数を記録すればいいです。 仮に残った数が 11 だった場合は、 NN は MM 個の因数を持たないので -1 を出力します。

M−1M-1 個の因数が出る前に残った数が 11 になってしまった場合も同様に、 NN は MM 個の因数を持たないので -1 を出力します。

割る数の上限についてですが、 NN を素因数分解して出る最大の素因数は N\sqrt{N} なので、 N\sqrt{N} まで繰り返してやれば問題なさそうです。 ただし、 sqrt() 関数を使うための <math.h> が使えないことに気をつけてください。

・入力例

  • N=420,M=4N=420, M=4 のケースを考えます。
  • 420420 は 22 で割れます。（残った数 210210 、因数 11 個） 2
  • 210210 は 22 で割れます。（残った数 105105 、因数 22 個） 2
  • 105105 は 22 で割れません。
  • 105105 は 33 で割れます。（残った数 3535 、因数 33 個） 3
  • 因数は今 M−1M-1 個となりました。残った数 35 を記録します。

最終的に 2 2 3 35 が出力されます。

int lim=(N/500)+150 というマジックナンバーは N<N500+150\sqrt{N} < \frac{N}{500} + 150 が成り立つもの（ルートの代用品）です。 N\sqrt{N} よりも大きく実行時間制限に間に合うものならなんでもOKです。

#include <stdio.h>

int main(void){
    int N, M;  scanf("%d%d", &N, &M);
    
    int lim=(N/500)+150;  // これ
    int count=0;
    _Bool flag=0;
    
    int ans[1000];
    
    for(int i=2; i<=lim; i++){
        
        if(count==M-1){
            flag=1;
            break;
        }
        
        if(N%i==0){
            ans[count]=i;
            
            N /= i;
            count++;
            i--;
        }
    }
    
    if(N==1){
        printf("-1\n");
        return 0;
    }
    else{
        if(flag){
            for(int i=0; i<M-1; i++) printf("%d ", ans[i]);
            
            printf("%d\n", N);
        }
        
        else{
            printf("-1\n");
            return 0;
        }
    }
}