9.14集训

今天做了几道数学题 第一道 hankson的趣味题

\(\because gcd(x,a_0)=a_1\)

\(\therefore \gcd(x/a_1,a_0/a_1)=1\)

\(\because lcm(x,b_0)=b_1\)

\(\therefore gcd(x,b_0) = x\times b_0 / lcm(x, b_0) = x\times b_0 / b_1\)

\(\therefore gcd(x/(x*b_0/b_1),b_0/(x*b_0/b_1))=1\)

\(\therefore gcd(b_1/b_0,b_1/x)=1\)

然后\(\sqrt n\)枚举约数，注意\(i \% a_1==0\)的条件

第二道是组合数问题

考虑前缀和

还有递推边界：\(f[0][0] =f[1][0]=f[0][1] =1\)

第三道货币系统

考虑筛

哪些数字不能被数组内的数字筛到，就得计数器++

用时间戳和桶来优化

第四道是解方程

运用秦九韶的结合律

第五道是Longge的问题

第六道是中国剩余定理(CRT)/曹冲养猪

第七道是能量采集

预处理出欧拉函数前缀和，然后用整除分块，这个题目就O(min⁡(n,m))地解决了。

还有一道是BZOJ的欧拉心算

\[\sum_{i=1}^n\sum_{j=1}^n\sum_{d=1}^n[gcd(i,j)=d]phi[d]\]

\[=\sum_{d=1}^nphi[d]*2\sum_{i=1}^{n/d}\sum_{j=1}^{n/d}(phi[i]-1)\]

咦？后边不就是仪仗队吗？