L1nxy's Blog

本来想写成题解的，但是这个实在没什么好写的。有算法的题目我一个没做来。
不要算法的题目看了七七八八。但是也没做出来几道。
距离上次参加cf已经过了几年了，心里其实一直很喜欢这个ac的感觉。于是打了一场div2。
不过至今记得当初那个没做来的
a题是真简单。水题。但是我思路不清，解了挺久的。其实就是一个模拟题目。很简单。超级简单。
b题目也不是很难，就是思路转换一下就行了。
c题把题目读错了，所以没做出来。英语太差了。
d题图论，看都没看就跳过了，图论我是真一点都不会。
后面的复盘我也没做之后的。太菜了。
好好加油。做完23个专题再看看吧。

题目不是很简单。
题意就是的找到给出区间内，所有，符合，这个数的约数的平方和等于另外一个数的平方的数。
难点在于如何求一个数的约数平方和。
具体还是看维基吧，我试图去理解，发现结果还有篇论文，只能当结论来记了。
维基百科
得到这个求和公式之后就好做多了。
对每一个数分解质因数就行了。

阅读剩余部分 -

这个题目就是把一个大数分解质因数。
方法有两个。
1,从最的小质因数开始，一个个去除，如果能整除，那么就是它的质因数之一，如果不能整除，那就把这个数加1。就算不是质数也没有关系，因为最小的质因数已经把之前的不是质数是部分给除掉了。
2.我选择了一个hard模式，用miller-rabin方法检测素数，用Pollard's rho方法去分解质因数，这个方法复杂度比上面那个低一点，但是不知道难写多少倍。。。。两天都用来debug这个东西 了。

Ref:
1.整数分解
2.Pollard's rho algorithm
3.素数检测

阅读剩余部分 -

这个题目挺有意思的，想了很久来怎么做，也查了很久。
这种形式的幂取模已经不太能用快速幂取模来求了。一来是幂运算是不支持交换律的，二来是如果算的话，数会很大。
这个题目的特别是，只求最后一位。
那么我们就能找规律。规律就是每一个数的N次方的个位数都只有4个数，并且在这4个数里循环。
并且我们可以加些优化，来保证结果。这个优化就是，可以简化成底数的最后两位来进行运算。
即x%100。
那么做法就是，把指数一个个从右往左的运算，然后对4取余。注意会有0的情况。
关键还是看代码吧。

fn main() {
    println!("Hello, world!");
}

fn cal_n(n: u64) -> i32 {
    if n < 4 {
        n as i32
    } else {
        (n % 4 + 4) as i32
    }
}

fn last_digit(lst: &[u64]) -> u64 {
    let mut n = 1u64;
    for i in lst.iter().rev() {
        let x = if *i >= 1000 { *i % 100 } else { *i };
        n = (x as f64).powi(if n < 4 {
            n as i32
        } else {
            (n % 4 + 4) as i32
        }) as u64;
    }
    n % 10
}

#[test]
fn basic_tests() {
    let tests = vec![
        (vec![], 1),
        (vec![0, 0], 1),
        (vec![0, 0, 0], 0),
        (vec![1, 2], 1),
        (vec![3, 4, 5], 1),
        (vec![4, 3, 6], 4),
        (vec![7, 6, 21], 1),
        (vec![12, 30, 21], 6),
        (vec![2, 2, 2, 0], 4),
        (vec![937640, 767456, 981242], 0),
        (vec![123232, 694022, 140249], 6),
        (vec![499942, 898102, 846073], 6)
    ];

    for test in tests {
        assert_eq!(last_digit(&test.0), test.1);
    }
}

一个6kyu的题目被我做出了4kyu的感觉。写了很久。也不是怪rust版本低，1.15。
说到底还是api不熟悉，本来都用函数试写了一次了，结果emmm，又重写推倒用普通过程式写了一次。真的麻烦。
还是多搞清楚所有权啥的吧。。

哎。我好菜。
其实就是一个parse .-的过程。
很简单。代码就不贴我的了。。。

阅读剩余部分 -