結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2020-02-09 12:02:19 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 57 ms / 2,000 ms |
コード長 | 3,872 bytes |
コンパイル時間 | 13,212 ms |
コンパイル使用メモリ | 387,120 KB |
実行使用メモリ | 17,544 KB |
最終ジャッジ日時 | 2024-10-01 05:49:58 |
合計ジャッジ時間 | 14,851 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#![allow(unused)]use std::io::{self, BufRead, Write};pub struct Input<R> {src: R,buf: Vec<u8>,pos: usize,}impl<R: BufRead> Input<R> {pub fn new(src: R) -> Self {Self {src,buf: Vec::new(),pos: 0,}}pub fn input_bytes(&mut self) -> &[u8] {loop {self.advance_until(|b| b.is_ascii_whitespace());if self.pos == self.buf.len() {self.buf.clear();self.src.read_until(b'\n', &mut self.buf).expect("input error");self.pos = 0;} else {break;}}let l = self.pos;self.advance_until(|b| !b.is_ascii_whitespace());&self.buf[l..self.pos]}fn advance_until(&mut self, f: impl Fn(u8) -> bool) {while let Some(b) = self.buf.get(self.pos) {if !f(*b) {break;}self.pos += 1;}}pub fn input<T: std::str::FromStr>(&mut self) -> Twhere<T as std::str::FromStr>::Err: std::fmt::Debug,{String::from_utf8_lossy(self.input_bytes()).parse().expect("parse error")}}pub fn mod_pow(a: i64, b: i64, m: i64) -> i64 {let mut b = b;let mut x = a;let mut y = 1;while b > 0 {if b & 1 == 1 {y = y * x % m;}x = x * x % m;b >>= 1;}y}pub fn mod_inv(x: i64, m: i64) -> i64 {mod_pow(x, m - 2, m)}struct Combination {m: i64,fact: Vec<i64>,}impl Combination {pub fn new(size: usize, m: i64) -> Self {let mut comb = Self {m,fact: Vec::new(),};comb.resize(size);comb}pub fn resize(&mut self, size: usize) {let old_len = self.fact.len();self.fact.resize(size + 1, 0);for i in old_len..size + 1 {self.fact[i] = if i == 0 {1} else {i as i64 * self.fact[i - 1] % self.m};}}pub fn fact(&self, x: i64) -> i64 {self.fact[x as usize]}pub fn perm(&self, a: i64, b: i64) -> i64 {if a >= b {self.fact(a) * mod_inv(self.fact(a - b), self.m) % self.m} else {0}}pub fn comb(&self, a: i64, b: i64) -> i64 {if a >= b {self.fact(a) * mod_inv(self.fact(b) * self.fact(a - b) % self.m, self.m) % self.m} else {0}}}pub fn gcd(x: i64, y: i64) -> i64 {if y > 0 {gcd(y, x % y)} else {x}}fn main() {let stdin = io::stdin();let mut input = Input::new(stdin.lock());let stdout = io::stdout();let mut out = io::BufWriter::new(stdout.lock());let stderr = io::stderr();let mut err = io::BufWriter::new(stderr.lock());const MOD: i64 = 1e9 as i64 + 7;let n = input.input();let k = input.input();let g = gcd(n, k);let mut mebious = vec![-2; g as usize + 1];mebious[0] = 0;mebious[1] = 0;for x in 2..=g as usize {if mebious[x] == -2 {mebious[x] = -1;for d in (2 * x..=g as usize).step_by(x) {mebious[d] = if d % (x * x) == 0 {0} else if mebious[d] == -2 {-1} else {-mebious[d]}}}}let mut ans = 0;let comb = Combination::new(n as usize, MOD);for d in 2..=g {if g % d == 0 {ans += MOD - mebious[d as usize] * comb.comb(n / d, k / d);ans %= MOD;}}writeln!(&mut out, "{}", ans);}