結果

問題 No.300 平方数
コンテスト
ユーザー @abcde
提出日時 2019-06-16 02:27:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 7 ms / 1,000 ms
コード長 1,337 bytes
コンパイル時間 1,820 ms
コンパイル使用メモリ 174,424 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-21 16:45:28
合計ジャッジ時間 3,083 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return ret: 素因数分解 の 結果 を 返却.
map<LL, int> div(LL X) {
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    map<LL, int> ret;
    while(X % 2 == 0) ret[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    for(LL i = 3; i <= sqrt(X); i += 2){
        while(X % i == 0){
            ret[i]++;
            X /= i;
        }
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ret[X]++;
    
    // 4. 出力.
    return ret;
}

int main() {
    
    // 1. 入力情報取得.
    LL X;
    scanf("%llu", &X);
    
    // 2. 与えられた正の整数について, 素因数分解を行う.
    map<LL, int> divisors = div(X);
    
    // 3. Y を 計算.
    LL ans = 1;
    for(auto &p : divisors) if(p.second % 2 == 1) ans *= p.first;

    // 4. 出力.
    // ex.
    // X = 123456789000
    // -> 137174210 で, OK ???.
    printf("%llu\n", ans);
    return 0;
    
}
0