blog.bouzuya.net

2023-03-10 ABC152 の A, B, C, D, E を解いた

ABC152 : AtCoder Beginner Contest 152 の A, B, C, D, E を解いた。

見覚えがあると思ったら 2023-03-01 に D まで解いていた。

use std::collections::HashMap;

use modint::ModInt1000000007 as ModInt;
use proconio::input;

fn prime_factorization(n: usize) -> Vec<(usize, usize)> {
    let mut p = vec![];
    if n < 2 {
        return p;
    }
    let mut n = n; // shadowing
    for i in 2.. {
        if i * i > n {
            break;
        }
        let mut c = 0;
        while n % i == 0 {
            c += 1;
            n /= i;
        }
        if c > 0 {
            p.push((i, c));
        }
    }
    if n != 1 {
        p.push((n, 1));
    }
    p
}

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    };
    let mut pq: HashMap<usize, usize> = HashMap::new();
    for a_i in a.iter().copied() {
        let ps = prime_factorization(a_i);
        for (p, q) in ps.iter().copied() {
            pq.entry(p).and_modify(|e| *e = (*e).max(q)).or_insert(q);
        }
    }
    let mut lcm = ModInt::new(1);
    for (p, q) in pq {
        lcm *= ModInt::new(p).pow(q as u64);
    }
    let mut sum = ModInt::new(0);
    for a_i in a {
        sum += lcm / a_i;
    }
    let ans = sum;
    println!("{}", ans);
}

// modint

Expo の Tutorial https://docs.expo.dev/tutorial/introduction/ を終えた。一応ストアの設定もしてみた。公開はしていない。次も小さいものをつくろうと思う。

『 Rust オープン社内勉強会』に参加した。 https://nifty.connpass.com/event/277493/

『 Nostr勉強会 #1 』に (登録していないけど YouTube の Live を見る形で) 参加した。 https://428lab.connpass.com/event/276333/

今日のコミット。