結果

問題 No.890 移調の限られた旋法
ユーザー cotton_fn_cotton_fn_
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#![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) -> T
where
<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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0