#569599 (Rust) No.1262 グラフを作ろう！

提出ソース

結果

問題	No.1262 グラフを作ろう！
ユーザー	koba-e964
提出日時	2020-10-22 19:59:47
言語	Rust (1.77.0)
結果	AC
実行時間	321 ms / 3,000 ms
コード長	2,339 bytes
コンパイル時間	4,084 ms
コンパイル使用メモリ	151,496 KB
実行使用メモリ	33,076 KB
最終ジャッジ日時	2023-09-28 14:48:34
合計ジャッジ時間	28,747 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	195 ms 19,336 KB
testcase_01	AC	142 ms 15,268 KB
testcase_02	AC	220 ms 23,852 KB
testcase_03	AC	167 ms 14,332 KB
testcase_04	AC	125 ms 21,072 KB
testcase_05	AC	142 ms 18,276 KB
testcase_06	AC	152 ms 24,352 KB
testcase_07	AC	37 ms 6,404 KB
testcase_08	AC	208 ms 25,668 KB
testcase_09	AC	111 ms 10,072 KB
testcase_10	AC	112 ms 13,000 KB
testcase_11	AC	232 ms 27,744 KB
testcase_12	AC	184 ms 17,744 KB
testcase_13	AC	177 ms 14,928 KB
testcase_14	AC	111 ms 13,960 KB
testcase_15	AC	86 ms 8,216 KB
testcase_16	AC	198 ms 24,340 KB
testcase_17	AC	174 ms 20,396 KB
testcase_18	AC	246 ms 26,464 KB
testcase_19	AC	117 ms 19,036 KB
testcase_20	AC	200 ms 27,000 KB
testcase_21	AC	232 ms 24,168 KB
testcase_22	AC	95 ms 17,180 KB
testcase_23	AC	114 ms 11,388 KB
testcase_24	AC	202 ms 25,408 KB
testcase_25	AC	66 ms 11,800 KB
testcase_26	AC	91 ms 14,144 KB
testcase_27	AC	163 ms 22,776 KB
testcase_28	AC	138 ms 19,608 KB
testcase_29	AC	135 ms 20,884 KB
testcase_30	AC	106 ms 14,576 KB
testcase_31	AC	208 ms 20,348 KB
testcase_32	AC	148 ms 17,188 KB
testcase_33	AC	52 ms 6,400 KB
testcase_34	AC	213 ms 27,256 KB
testcase_35	AC	165 ms 15,376 KB
testcase_36	AC	56 ms 6,136 KB
testcase_37	AC	245 ms 26,932 KB
testcase_38	AC	164 ms 21,136 KB
testcase_39	AC	108 ms 10,328 KB
testcase_40	AC	113 ms 12,704 KB
testcase_41	AC	160 ms 22,920 KB
testcase_42	AC	230 ms 26,464 KB
testcase_43	AC	138 ms 18,548 KB
testcase_44	AC	141 ms 17,316 KB
testcase_45	AC	243 ms 28,000 KB
testcase_46	AC	178 ms 25,944 KB
testcase_47	AC	110 ms 9,740 KB
testcase_48	AC	201 ms 24,312 KB
testcase_49	AC	241 ms 25,944 KB
testcase_50	AC	236 ms 26,424 KB
testcase_51	AC	137 ms 12,168 KB
testcase_52	AC	170 ms 24,836 KB
testcase_53	AC	59 ms 9,316 KB
testcase_54	AC	193 ms 18,296 KB
testcase_55	AC	157 ms 17,188 KB
testcase_56	AC	147 ms 21,896 KB
testcase_57	AC	281 ms 30,436 KB
testcase_58	AC	172 ms 16,132 KB
testcase_59	AC	157 ms 23,032 KB
testcase_60	AC	261 ms 28,504 KB
testcase_61	AC	106 ms 13,028 KB
testcase_62	AC	217 ms 23,296 KB
testcase_63	AC	190 ms 16,956 KB
testcase_64	AC	144 ms 16,264 KB
testcase_65	AC	84 ms 14,060 KB
testcase_66	AC	112 ms 14,052 KB
testcase_67	AC	110 ms 16,392 KB
testcase_68	AC	165 ms 25,648 KB
testcase_69	AC	108 ms 15,460 KB
testcase_70	AC	230 ms 28,304 KB
testcase_71	AC	181 ms 22,072 KB
testcase_72	AC	250 ms 28,792 KB
testcase_73	AC	243 ms 25,676 KB
testcase_74	AC	204 ms 20,924 KB
testcase_75	AC	202 ms 23,464 KB
testcase_76	AC	173 ms 21,448 KB
testcase_77	AC	202 ms 22,144 KB
testcase_78	AC	202 ms 24,096 KB
testcase_79	AC	272 ms 30,104 KB
testcase_80	AC	231 ms 28,732 KB
testcase_81	AC	197 ms 21,672 KB
testcase_82	AC	231 ms 24,080 KB
testcase_83	AC	215 ms 27,180 KB
testcase_84	AC	178 ms 21,864 KB
testcase_85	AC	277 ms 30,308 KB
testcase_86	AC	209 ms 23,568 KB
testcase_87	AC	247 ms 27,728 KB
testcase_88	AC	198 ms 21,408 KB
testcase_89	AC	201 ms 25,928 KB
testcase_90	AC	318 ms 33,060 KB
testcase_91	AC	302 ms 33,072 KB
testcase_92	AC	306 ms 33,076 KB
testcase_93	AC	321 ms 33,068 KB
testcase_94	AC	304 ms 33,076 KB
testcase_95	AC	297 ms 33,068 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        a: [usize],
    }
    let n = n + 1;
    // Problem: find \sum_{x: a} \sum_{j = 1}^x (gcd(x, j) - 1)
    let mut phi = vec![1i64; n];
    let mut fac = vec![0; n];
    for i in 1..n {
        fac[i] = i;
    }
    for i in 2..n {
        if fac[i] != i {
            continue;
        }
        for j in 2..(n - 1) / i + 1 {
            fac[i * j] = i;
        }
    }
    for i in 1..n {
        let mut v = i;
        let mut a = 1;
        while v > 1 {
            let p = fac[v];
            let mut e = 0;
            while v % p == 0 {
                e += 1;
                v /= p;
            }
            a *= p - 1;
            for _ in 0..e - 1 {
                a *= p;
            }
        }
        phi[i] = a as i64;
    }
    // \sum_[j = 1}^x gcd(x, i) = \sum_{g | x} g * phi(x / g)
    let mut vals = vec![0; n];
    for g in 1..n {
        for j in 1..(n - 1) / g + 1 {
            vals[g * j] += g as i64 * phi[j];
        }
    }
    let mut tot = 0;
    // (RHS) = \sum {x: a} vals[x] - x
    for a in a {
        tot += vals[a] - a as i64;
    }
    println!("{}", tot);
}

yukicoder

結果

テストケース

ソースコード