結果
問題 | No.2193 メガの下1桁 |
ユーザー | akakimidori |
提出日時 | 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 | - |
ソースコード
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 IwhereI: 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}