結果

問題 No.1022 Power Equation
コンテスト
ユーザー akakimidori
提出日時 2020-04-10 22:20:06
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 295 ms / 2,000 ms
コード長 1,282 bytes
コンパイル時間 17,180 ms
コンパイル使用メモリ 377,544 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 20:49:30
合計ジャッジ時間 17,451 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;
use std::io::Write;

fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn lcm(a: u64, b: u64) -> u64 {
    a / gcd(a, b) * b
}

fn run() {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    it.next();
    for s in it {
        let n: u64 = s.parse().unwrap();
        let mut ans = n * n;// a = c = 1
        if n > 1 {
            ans += (n - 1) * n;// a = c > 1
        }
        let mut set = std::collections::BTreeSet::new();
        // a > c > 1
        for r in 2u64.. {
            if r.pow(2) > n {
                break;
            }
            for a in 2u64.. {
                if r.pow(a as u32) > n {
                    break;
                }
                for c in 1u64..a {
                    let (p, q) = (r.pow(a as u32), r.pow(c as u32));
                    if set.insert((p, q)) {
                        let x = lcm(a, c);
                        ans += 2 * (n / (x / c));
                    }
                }
            }
        }
        writeln!(out, "{}", ans).ok();
    }
}

fn main() {
    run();
}
0