結果

問題 No.3365 Prefix and Suffix X
コンテスト
ユーザー akakimidori
提出日時 2025-11-17 21:46:02
言語 Rust
(1.83.0 + proconio)
結果
RE  
実行時間 -
コード長 3,969 bytes
コンパイル時間 15,849 ms
コンパイル使用メモリ 403,816 KB
実行使用メモリ 9,780 KB
最終ジャッジ日時 2025-11-17 21:46:29
合計ジャッジ時間 16,435 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 5 RE * 25
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `v`
  --> src/main.rs:18:17
   |
18 |             let v = y.iter().fold(0, |s, a| s * 10 + (*a - b'0') as i64);
   |                 ^ help: if this is intentional, prefix it with an underscore: `_v`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `b`
  --> src/main.rs:61:17
   |
61 |         let (a, b) = calc(p, m);
   |                 ^ help: if this is intentional, prefix it with an underscore: `_b`

warning: type alias `Map` is never used
 --> src/main.rs:5:6
  |
5 | type Map<K, V> = BTreeMap<K, V>;
  |      ^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: type alias `Set` is never used
 --> src/main.rs:6:6
  |
6 | type Set<T> = BTreeSet<T>;
  |      ^^^

warning: type alias `Deque` is never used
 --> src/main.rs:7:6
  |
7 | type Deque<T> = VecDeque<T>;
  |      ^^^^^

ソースコード

diff # 

use std::io::Write;
use std::collections::*;

type Map<K, V> = BTreeMap<K, V>;
type Set<T> = BTreeSet<T>;
type Deque<T> = VecDeque<T>;

fn run() {
    input! {
        t: usize,
        ask: [(bytes, i64); t],
    }
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    for (x, m) in ask {
        if let Some(y) = solve(x, m) {
            let v = y.iter().fold(0, |s, a| s * 10 + (*a - b'0') as i64);
            writeln!(out, "{}", y.iter().map(|c| *c as char).collect::<String>()).ok();
        } else {
            writeln!(out, "-1").ok();
        }
    }
}

fn main() {
    run();
}

fn solve(x: Vec<u8>, m: i64) -> Option<Vec<u8>> {
    let v = x.iter().fold(0, |s, a| s * 10 + (*a - b'0') as i64);
    let l = x.len();
    for i in l..=18 {
        if i < 2 * l {
            let mut ans = vec![b'0' - 1; i];
            for j in 0..l {
                ans[j] = x[j];
            }
            for j in 0..l {
                if ans[i - l + j] != b'0' - 1 && ans[i - l + j] != x[j] {
                    break;
                }
                ans[i - l + j] = x[j];
            }
            if ans.iter().all(|a| *a >= b'0') && ans.iter().fold(0, |s, a| s * 10 + (*a - b'0') as i64) % m == 0 {
                return Some(ans);
            }
            continue;
        }
        let f = i - 2 * l;
        let rhs = (-v * (1 + 10i64.pow(i as u32 - l as u32))).rem_euclid(m);
        // 10^l * A = rhs (mod M)
        let p = 10i64.pow(l as u32);
        let g = gcd(p, m);
        if rhs % g != 0 {
            continue;
        }
        let p = p / g;
        let rhs = rhs / g;
        let m = m / g;
        let (a, b) = calc(p, m);
        assert!(p * a % m == 1);
        let mut r = (rhs * a).rem_euclid(m);
        if r >= 10i64.pow(f as u32) {
            continue;
        }
        let mut ans = vec![b'0'; i];
        for j in 0..l {
            ans[j] = x[j];
            ans[i - l + j] = x[j];
        }
        for a in ans[l..(i - l)].iter_mut().rev() {
            *a = b'0' + (r % 10) as u8;
            r /= 10;
        }
        return Some(ans)
    }
    None
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a.abs()
    } else {
        gcd(b, a.rem_euclid(b.abs()))
    }
}

// return (a, b)
// ax + by = gcd(x, y)
fn calc(x: i64, y: i64) -> (i64, i64) {
    if y == 0 {
        return (x.signum(), 0);
    }
    let q = x.div_euclid(y);
    let r = x.rem_euclid(y);
    let p = calc(y, r);
    (p.1, p.0 - q * p.1)
}

// ---------- 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 ----------
0