20230710

发布时间 2023-07-27 15:01:49作者: 星河倒注

T1 Strange Limit

题意:

给你两个数p,m,计算bn的极限,其中bn等于an对m的阶乘取模,而an = ppp...

解法:

欧拉定理直接递归求解就行了

T2 GCD Determinant

题意:

求一个gcd矩阵行列式的值

解法:

Smith在1875年首次证明了以下结果:

结论题

T4 矩阵游戏P1397

题意:

自己去看

解法:

首先这个东西其实就是求(A的m-1次方* B)的n-1次方* A的m-1次方
这个式子可以使用矩阵快速幂。对于同一行,构造:

【a 0】

【b 1】

对于同一列可以构造:

【c 0】

【d 1】

按矩阵快速幂搞就行了

T5 Remainders Game

题意:

给定n个数字,使得一个x使得x对这n个数取模的值固定,给定一个数k,问x除以k的余数是否恒定。

解法:

显然有一个结论就是对于满足对c1,c2....cn模数固定的x,x+gcd(c1,c2....,cn)肯定也满足条件,这告诉我们x对gcd(c1,c2,....,cn)取模为定值。所以显然当且仅当gcd(c1,c2,......cn)对k取模为0时,x对k取模为定值。

T6 Power Tower

没什么好说的,跟T1都是扩展欧拉定理板题

T8 Border

题意:

火星上的钞票面额有\(n\)种,第\(i\)种的价值是\(a_i\)。$Natasha $ 每个面额的钞票都有无数张。

火星人有\(k\)个手指,所以他们使用\(k\)进制。此外,火星人认为数字\(d\)(在\(k\)进制中)是神圣的。因此,如果凑出来的钱中在\(k\)进制中最后一位数字是\(d\),火星人会很高兴。不幸的是,$Natasha $ 还不知道\(d\)是几。所以,他想知道他能凑出哪些数字。

解法:

首先显然选择的面额之和肯定是d=gcd(a1,a2....,an)的倍数设凑出的数字为c,设总和为dx,那么显然有dx与c modk同余。根据裴蜀定理,c为gcd(d,k)的倍数,有k/gcd(d,k)种c的值