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的值