結果

問題 No.36 素数が嫌い！
コンテスト
ユーザー @abcde
提出日時 2019-06-01 23:01:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 87 ms / 5,000 ms
コード長 1,774 bytes
コンパイル時間 1,653 ms
コンパイル使用メモリ 173,840 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-17 20:00:45
合計ジャッジ時間 3,460 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数.
vector<LL> div(LL X){
    vector<LL> ret;
    ret.push_back(1);
    for(LL d = 2; d * d <= X; d++) {
        if(X % d == 0) {
            ret.push_back(d);
            if(d * d != X) ret.push_back(X / d);
        }
    }
    ret.push_back(X);
    sort(ret.begin(), ret.end());
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    LL N;
    scanf("%llu", &N);
    
    // 2. N を 素因数分解.
    vector<LL> divisors = div(N);
    // for(auto &p : divisors) cout << p << " ";
    
    // 3. 友達の前で使っても良い整数であるか確認.
    // ex.
    // N = 4
    // 1, 2, 4 -> NO
    // 
    // N = 27
    // 1, 3, 9, 27 -> YES
    // 
    // N = 99999640000243
    // 1, 9999973, 9999991, 99999640000243 -> NO
    // 
    // -> 1 と 自身 以外について, 以下の判定を入れればよいかどうか？
    // ① サイズ が 3以上 ならば, OK.
    // ② サイズ が 2     ならば, a < b と置いたとき, b =  a * a ならば, OK.
    // ③ サイズ が 2     ならば, a < b と置いたとき, b != a * a ならば, NG.
    // ④ サイズ が 1以下 ならば, NG.
    bool ans = false;
    if(divisors.size() >= 5) ans = true;
    if(divisors.size() == 4){
        LL a = divisors[1];
        LL b = divisors[2];
        // cout << a << " " << b << endl;
        if(b == a * a) ans = true;
        else           ans = false;
    }
    if(divisors.size() <= 3) ans = false;

    // 4. 後処理.
    if(ans) printf("%s\n", "YES");
    else    printf("%s\n", "NO");
    return 0;
    
}
0