#1025086 (Rust) No.2954 Calculation of Exponentiation

• 問題: No.2954 Calculation of Exponentiation
• ユーザー: Moss_Local
• 提出日時: 2024-11-08 21:57:10
• 言語: Rust (1.77.0 + proconio)
• 結果: WA
• 実行時間: -
• コード長: 6,506 bytes
• コンパイル時間: 14,374 ms
• コンパイル使用メモリ: 378,060 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-08 21:57:26
• 合計ジャッジ時間: 15,630 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	WA	-
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	WA	-
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	1 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	AC	1 ms; 5,248 KB
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	AC	1 ms; 5,248 KB
testcase_27	WA	-
testcase_28	AC	1 ms; 5,248 KB
testcase_29	AC	1 ms; 5,248 KB
testcase_30	AC	1 ms; 5,248 KB

コンパイルメッセージ

warning: variable does not need to be mutable
   --> src/main.rs:110:9
    |
110 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:116:9
    |
116 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:121:9
    |
121 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:127:9
    |
127 |     let mut vec: Vec<f64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:132:9
    |
132 |     let mut vec: Vec<char> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:137:9
    |
137 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:142:9
    |
142 |     let mut vec: Vec<i64> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:148:9
    |
148 |     let mut vec: Vec<usize> = read_vec();
    |         ----^^^
    |         |
    |         help: remove this `mut`

ソースコード

#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]

use std::cmp::*;
use std::fmt::*;
use std::hash::*;
use std::io::BufRead;
use std::iter::FromIterator;
use std::*;
use std::{cmp, collections, fmt, io, iter, ops, str};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD1: i64 = 1000000007;
const MOD9: i64 = 998244353;
const MOD: i64 = MOD9;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;

use cmp::Ordering::*;
use std::collections::*;

use std::io::stdin;
use std::io::stdout;
use std::io::Write;

macro_rules! p {
    ($x:expr) => {
        println!("{}", $x);
    };
}

macro_rules! vp {
    ($x:expr) => {
        println!(
            "{}",
            $x.iter()
                .map(|x| x.to_string())
                .collect::<Vec<_>>()
                .join(" ")
        );
    };
}

macro_rules! d {
    ($x:expr) => {
        eprintln!("{:?}", $x);
    };
}
macro_rules! yn {
    ($val:expr) => {
        if $val {
            println!("Yes");
        } else {
            println!("No");
        }
    };
}

macro_rules! map{

    ($($key:expr => $val:expr),*) => {
        {
            let mut map = ::std::collections::BTreeMap::new();
            $(
                map.insert($key, $val);
            )*
            map
        }
    };
}

macro_rules! set{

    ($($key:expr),*) => {
        {
            let mut set = ::std::collections::BTreeSet::new();
            $(
                set.insert($key);
            )*
            set
        }
    };
}

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

#[allow(dead_code)]
fn readii() -> (i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1])
}

#[allow(dead_code)]
fn readff() -> (f64, f64) {
    let mut vec: Vec<f64> = read_vec();
    (vec[0], vec[1])
}

fn readcc() -> (char, char) {
    let mut vec: Vec<char> = read_vec();
    (vec[0], vec[1])
}

fn readuuu() -> (usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
    let mut vec: Vec<i64> = read_vec();
    (vec[0], vec[1], vec[2], vec[3])
}

#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
    let mut vec: Vec<usize> = read_vec();
    (vec[0], vec[1], vec[2], vec[3])
}

fn gcd(mut a: i64, mut b: i64) -> i64 {
    while b != 0 {
        let temp = a % b;
        a = b;
        b = temp;
    }
    a.abs()
}

fn parse_fraction(s: &str) -> (i64, i64) {
    if let Some(dot_pos) = s.find('.') {
        let decimal_digits = s.len() - dot_pos - 1;
        let decimal_digits = decimal_digits.min(4);
        let scale = 10_i64.pow(decimal_digits as u32);
        let numerator: i64 = s.replace(".", "").parse().unwrap();
        let denominator = scale;
        let common_gcd = gcd(numerator.abs(), denominator);
        (numerator / common_gcd, denominator / common_gcd)
    } else {
        let numerator: i64 = s.parse().unwrap();
        (numerator, 1)
    }
}

fn factorize(mut n: i64) -> Vec<(i64, i64)> {
    let mut factors = Vec::new();

    let small_primes = [
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89,
        97,
    ];
    for &p in &small_primes {
        if p * p > n {
            break;
        }
        let mut count = 0;
        while n % p == 0 {
            count += 1;
            n /= p;
        }
        if count > 0 {
            factors.push((p, count));
        }
    }

    let mut p = 101;
    while p * p <= n {
        if n % p == 0 {
            let mut count = 0;
            while n % p == 0 {
                count += 1;
                n /= p;
            }
            factors.push((p, count));
        }
        p += 2;
    }
    if n > 1 {
        factors.push((n, 1));
    }
    factors
}

fn check_perfect_power(factors: &Vec<(i64, i64)>, d: i64) -> bool {
    for &(_, exp) in factors {
        if exp % d != 0 {
            return false;
        }
    }
    true
}

fn compute_root(factors: &Vec<(i64, i64)>, d: i64) -> i64 {
    let mut res = 1;
    for &(p, e) in factors {
        res *= p.pow((e / d) as u32);
    }
    res
}

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();

    if let Some(Ok(line)) = lines.next() {
        let parts: Vec<&str> = line.trim().split_whitespace().collect();
        if parts.len() != 2 {
            println!("No");
            return;
        }
        let a_str = parts[0];
        let b_str = parts[1];

        let (a_num, a_den) = parse_fraction(a_str);
        let (b_num, b_den) = parse_fraction(b_str);

        let gcd_a = gcd(a_num.abs(), a_den);
        let a_reduced = (a_num / gcd_a, a_den / gcd_a);

        let gcd_b = gcd(b_num.abs(), b_den);
        let b_reduced = (b_num / gcd_b, b_den / gcd_b);
        let a1 = a_reduced.0;
        let a2 = a_reduced.0;
        let b1 = b_reduced.0;
        let b2 = b_reduced.1;
        let factors_a = factorize(a1);
        let mut map_a = BTreeMap::new();
        for (p, e) in factors_a {
            map_a.insert(p, e * b1); //pow b1
        }

        let factors_a2 = factorize(a2);
        for (p, e) in factors_a2 {
            if !map_a.contains_key(&p) {
                p!("No");
                return;
            } else {
                let e2 = *map_a.get(&p).unwrap();
                if e > e2 {
                    p!("No");
                    return;
                }
                map_a.insert(p, e2 - e);
            }
        }
        for &e in map_a.values() {
            if e % b2 != 0 {
                p!("No");
                return;
            }
        }
        p!("Yes");
    } else {
        println!("No");
    }
}