結果

問題 No.546 オンリー・ワン
コンテスト
ユーザー hatoo
提出日時 2017-10-12 18:52:19
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 3,057 bytes
コンパイル時間 13,520 ms
コンパイル使用メモリ 379,796 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-17 10:53:50
合計ジャッジ時間 13,987 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff # 

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{HashMap, HashSet};

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn get<T: FromStr>() -> T
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }

    #[allow(dead_code)]
    pub fn get2<T: FromStr, U: FromStr>() -> (T, U)
    where
        <T as FromStr>::Err: Debug,
        <U as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    }

    #[allow(dead_code)]
    pub fn get3<S: FromStr, T: FromStr, U: FromStr>() -> (S, T, U)
    where
        <S as FromStr>::Err: Debug,
        <T as FromStr>::Err: Debug,
        <U as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        let mut iter = line.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    }
}


#[allow(unused_macros)]
macro_rules! debug {
    ($x: expr) => {
        println!("{}: {:?}", stringify!($x), $x)
    }
}

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


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

fn n_d(l: usize, r: usize, d: usize) -> usize {
    r / d - (l - 1) / d
}

fn main() {
    let (_n, l, h): (usize, usize, usize) = util::get3();
    let c: Vec<usize> = util::gets();

    let mut ans = 0;
    for i in 0..c.len() {
        let d = c[i];
        let others: Vec<usize> = (0..c.len()).filter(|&k| k != i).map(|k| c[k]).collect();
        let mut a = 0i64;
        for k in 0..1 << others.len() {
            let mut m = d;
            let mut bits = 1;
            for j in 0..others.len() {
                if k >> j & 1 == 1 {
                    bits += 1;
                    m = lcm(m, others[j]);
                }
            }
            if bits % 2 == 0 {
                a -= n_d(l, h, m) as i64;
            } else {
                a += n_d(l, h, m) as i64;
            }
        }
        ans += a;
    }

    println!("{}", ans);
}
0