結果

問題 No.2193 メガの下1桁
ユーザー akakimidoriakakimidori
提出日時 2023-01-13 22:57:40
言語 Rust
(1.77.0 + proconio)
結果
WA  
実行時間 -
コード長 3,970 bytes
コンパイル時間 16,704 ms
コンパイル使用メモリ 392,004 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-12-24 18:57:14
合計ジャッジ時間 18,021 ms
ジャッジサーバーID
(参考情報)
judge4 / judge2
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,820 KB
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,824 KB
testcase_03 AC 1 ms
6,816 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 1 ms
6,816 KB
testcase_07 AC 1 ms
6,816 KB
testcase_08 AC 1 ms
6,816 KB
testcase_09 AC 1 ms
6,816 KB
testcase_10 AC 1 ms
6,816 KB
testcase_11 AC 1 ms
6,816 KB
testcase_12 AC 1 ms
6,820 KB
testcase_13 AC 1 ms
6,820 KB
testcase_14 AC 1 ms
6,820 KB
testcase_15 AC 1 ms
6,820 KB
testcase_16 AC 1 ms
6,816 KB
testcase_17 AC 1 ms
6,816 KB
testcase_18 WA -
testcase_19 AC 1 ms
6,816 KB
testcase_20 AC 1 ms
6,816 KB
testcase_21 AC 1 ms
6,816 KB
testcase_22 AC 1 ms
6,820 KB
testcase_23 AC 2 ms
6,816 KB
testcase_24 AC 1 ms
6,820 KB
testcase_25 AC 1 ms
6,816 KB
testcase_26 AC 1 ms
6,816 KB
testcase_27 AC 1 ms
6,816 KB
testcase_28 AC 1 ms
6,816 KB
testcase_29 AC 1 ms
6,816 KB
testcase_30 AC 1 ms
6,816 KB
testcase_31 AC 1 ms
6,816 KB
testcase_32 AC 1 ms
6,820 KB
testcase_33 AC 1 ms
6,820 KB
testcase_34 AC 1 ms
6,820 KB
testcase_35 AC 1 ms
6,820 KB
testcase_36 AC 2 ms
6,816 KB
testcase_37 AC 1 ms
6,816 KB
testcase_38 AC 1 ms
6,816 KB
testcase_39 WA -
権限があれば一括ダウンロードができます

ソースコード

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

fn main() {
input! {
m: usize,
d: usize,
n: usize,
b: usize,
}
let modulo = b * phi(b);
let normalize = |a: usize| {
if a >= modulo {
a % modulo + modulo
} else {
a
}
};
let pow = |mut r: usize, mut n: usize| -> usize {
let mut t = 1;
r = normalize(r);
while n > 0 {
if n & 1 == 1 {
t = normalize(t * r);
}
r = normalize(r * r);
n >>= 1;
}
t
};
let shift = |m: usize| -> usize {
pow(normalize(m + d), m)
};
let mut m = normalize(m);
let mut n = n;
let mut t = 0usize;
let mut pre = vec![None; 2 * modulo];
while n > 0 {
if let Some(s) = pre[m] {
n %= t - s;
} else {
pre[m] = Some(t);
}
if n > 0 {
m = shift(m);
n -= 1;
t += 1;
}
}
if m % b == 10 {
println!("A");
} else {
println!("{}", m % b);
}
}
fn phi(a: usize) -> usize {
let mut res = a;
for i in 2..=a {
if a % i == 0 {
res -= res / i;
}
}
res
}
mod util {
pub trait Join {
fn join(self, sep: &str) -> String;
}
impl<T, I> Join for I
where
I: Iterator<Item = T>,
T: std::fmt::Display,
{
fn join(self, sep: &str) -> String {
let mut s = String::new();
use std::fmt::*;
for (i, v) in self.enumerate() {
if i > 0 {
write!(&mut s, "{}", sep).ok();
}
write!(&mut s, "{}", v).ok();
}
s
}
}
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// floor(a ^ (1 / k))
pub fn kth_root(a: u64, k: u64) -> u64 {
assert!(k > 0);
if a == 0 {
return 0;
}
if k >= 64 {
return 1;
}
if k == 1 {
return a;
}
let valid = |x: u64| -> bool {
let mut t = x;
for _ in 1..k {
let (val, ok) = t.overflowing_mul(x);
if !(!ok && val <= a) {
return false;
}
t = val;
}
true
};
let mut ok = 1;
let mut ng = 2;
while valid(ng) {
ok = ng;
ng *= 2;
}
while ng - ok > 1 {
let mid = ok + (ng - ok) / 2;
if valid(mid) {
ok = mid;
} else {
ng = mid;
}
}
ok
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0