#815948 (Rust) No.1731 Product of Subsequence

• 問題: No.1731 Product of Subsequence
• ユーザー: phspls
• 提出日時: 2022-11-13 12:56:52
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 968 ms / 2,000 ms
• コード長: 1,197 bytes
• コンパイル時間: 14,260 ms
• コンパイル使用メモリ: 379,304 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-09-14 20:24:15
• 合計ジャッジ時間: 22,194 ms
• ジャッジサーバーID （参考情報）: judge3 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	605 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	26 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	827 ms; 5,376 KB
testcase_11	AC	709 ms; 5,376 KB
testcase_12	AC	2 ms; 5,376 KB
testcase_13	AC	21 ms; 5,376 KB
testcase_14	AC	651 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	522 ms; 5,376 KB
testcase_19	AC	16 ms; 5,376 KB
testcase_20	AC	435 ms; 5,376 KB
testcase_21	AC	968 ms; 5,376 KB
testcase_22	AC	1 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB
testcase_24	AC	20 ms; 5,376 KB
testcase_25	AC	8 ms; 5,376 KB
testcase_26	AC	152 ms; 5,376 KB
testcase_27	AC	196 ms; 5,376 KB
testcase_28	AC	388 ms; 5,376 KB
testcase_29	AC	160 ms; 5,376 KB
testcase_30	AC	571 ms; 5,376 KB
testcase_31	AC	2 ms; 5,376 KB
testcase_32	AC	1 ms; 5,376 KB
testcase_33	AC	2 ms; 5,376 KB
testcase_34	AC	42 ms; 5,376 KB

コンパイルメッセージ

warning: unused variable: `n`
  --> src/main.rs:14:9
   |
14 |     let n = nk[0];
   |         ^ help: if this is intentional, prefix it with an underscore: `_n`
   |
   = note: `#[warn(unused_variables)]` on by default

ソースコード

use std::collections::HashMap;

const MOD: usize = 1e9 as usize + 7;

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

fn main() {
    let mut nk = String::new();
    std::io::stdin().read_line(&mut nk).ok();
    let nk: Vec<usize> = nk.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();
    let n = nk[0];
    let k = nk[1];
    let mut a = String::new();
    std::io::stdin().read_line(&mut a).ok();
    let a: Vec<usize> = a.trim().split_whitespace().map(|s| s.parse().unwrap()).collect();

    let mut dp = HashMap::new();
    dp.insert(1, 1usize);
    for &v in a.iter() {
        let mut next_dp = HashMap::new();
        for (&gcdval, &cnt) in dp.iter() {
            *next_dp.entry(gcdval).or_insert(0usize) += cnt;
            *next_dp.entry(gcdval).or_insert(0usize) %= MOD;
            let val = gcd(v, k);
            let val = gcd(gcdval*val, k);
            *next_dp.entry(val).or_insert(0usize) += cnt;
            *next_dp.entry(val).or_insert(0usize) %= MOD;
        }
        dp = next_dp;
    }
    if k == 1 {
        println!("{}", dp.get(&k).unwrap()-1);
    } else {
        println!("{}", dp.get(&k).unwrap_or(&0));
    }
}