没几道题，却做了很长时间。有几个很水的题，但大部分质量很高，尤其是最后做的三四个题，把我写吐了。 题单地址：[kuangbin带你飞]专题1-23
LightOJ 1370 Bi-shoe and Phi-shoe
筛法得到欧拉函数的值
代码
1 | |
LightOJ 1341 Aladdin and the Flying Carpet
网上很多代码对$1-b$进行循环，复杂度是不正确的。由于$a$的素因数最多只有$\log_{2}a$个。设$a=p_1^{k_1}p_1^{k_2}…p_1^{k_n}$，由基本不等式$k_1k_2..k_n<=(\frac{k_1+k_2…+k_n}{n})^2<=(\frac{\log_{2}a}{n})^2$，可知a的所有素因数个数的乘积不会太大，所以可以用$dfs$枚举$a$所有可能的因数。
代码
1 | |
LightOJ 1336 Sigma Function
将题目所给公式化简为$\sigma(n)=(1+p_1+..+p_1^{e_1})(1+p_2+..+p_2^{e_2})…(1+p_k+..+p_k^{e_k})$，如果要让$\sigma(n)$为奇数，由于当$p_k$为2时，$(1+p_k+..+p_k^{e_k})$一定为奇数，所以剩下的素因子的指数应该都是偶数，这样当2的指数也是偶数时，$n$是某个数的平方。当2的指数是奇数时，如果其余素因子的指数是偶数，应该有$n/2$是某个数的平方。综上$\sigma(n)$是奇数的条件就是$n$是某个数的平方或$n/2$是某个数的平方。这个题即输出$n-\sqrt{n}-\sqrt{n/2}$
代码
1 | |
LightOJ 1282 Leading and Trailing
后三位用快速幂对$n^k$模1000就可以了。计算前三位时把原数变形为$n^k=10^{\log_{10}a^k}=10^{k\log_{10}a}$，用$x，y$表示$k\log_{10}a$的整数部分与小数部分，可得$n^k=10^{x+y}=10^x*10^y$，则$n^k$的位数是由$10^x$决定的，各位数字是由$10^y$决定的，而$0\leq y<1$，所以$1\leq 10^y<10$，$10^y *100$的整数部分就是$n^k$的前三位。
代码
1 | |
LightOJ 1259 Goldbach`s Conjecture
把1e7以内的素数先筛出来，之后每个数枚举一下就行了。
代码
1 | |
LightOJ 1245 Harmonic Number (II)
数论分块
代码
1 | |
LightOJ 1236 Pairs Forming LCM
\[\begin{aligned} &设\,\,a=p_1^{k_{a1}}p_2^{k_{a2}}...p_s^{k_{as}},\,\,b=p_1^{k_{b1}}p_2^{k_{b2}}...p_s^{k_{bs}}\\ &有\,\,gcd(a,b)=p_1^{min(k_{a1},k_{b1})}p_2^{min(k_{a2},k_{b2})}...p_s^{min(k_{as},k_{bs})}\\ &\quad lcm(a,b)=p_1^{max(k_{a1},k_{b1})}p_2^{max(k_{a2},k_{b2})}...p_s^{max(k_{as},k_{bs})}\\ \end{aligned}\]设$n=p_1^{k_1}p_2^{k_2}…p_m^{k_m}$，由上述式子不难得出$\forall 1\leq i,j\leq n$，使$lcm(i,j)=n$的方案数有$sum=(2k_1+1)(2k_2+1)…(2*k_m+1)$种，而本题要求$1\leq i\leq j\leq n$，所以方案数为$(sum+1)/2$（分子加一是考虑到$i=j$的情况）
代码
1 | |
LightOJ 1234 Harmonic Number
直接暴力可以跑出来，但是数组开不到1e8，可以每50个数分一块，这样每次查询最多再跑49次就可以了。
代码
1 | |
LightOJ 1220 Mysterious Bacteria
唯一分解定理后取指数项最小值即可。注意当n为负数时，答案一定为奇数，所以要将结果一直除二直到变为奇数。
代码
1 | |
LightOJ 1214 Large Division
高精度模板
代码
1 | |
LightOJ 1213 Fantasy of a Summation
推式子，$res=kn^{k-1}sum$
代码
1 | |
LightOJ 1197 Help Hanzo
区间素数模板
代码
1 | |
LightOJ 1138 Trailing Zeroes (III)
$n!$后几位中0的个数其实就是$n!$因数中$5$的个数，不难推出对于一个确定的n，$n!$中后几位0的个数为$\frac{n}{5}+\frac{n}{5^2}+\frac{n}{5^3}+…$
二分答案即可
代码
1 | |
UVA 11426 GCD - Extreme (II)
\[\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^ngcd(i,j)\\ =&\sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^n[gcd(i,j)=k]\\ =&\sum_{k=1}^nk\sum_{i=1}^{n/k}\sum_{j=1}^{n/k}[gcd(i,j)=1]\\ =&\sum_{k=1}^nk\sum_{i=1}^{n/k}\sum_{j=1}^{n/k}\sum_{m|gcd(i,j)}\mu(m)\\ =&\sum_{k=1}^nk\sum_{m=1}^{n}\mu(m)*\frac{n}{km}*\frac{n}{km}\\ =&\sum_{D=1}^n\sum_{k|D}k*\mu(\frac{D}{m})*\frac{n}{D}*\frac{n}{D}\\ =&\sum_{D=1}^n\psi(D)*\frac{n}{D}*\frac{n}{D}\\ \end{aligned}\]筛出欧拉函数后分块计算即可
代码
1 | |
POJ 1061 青蛙的约会
题目即求$x-y+p(m-n)=qL$，转化为$(m-n)x+Ly=y-x\quad(m>n)$形式用$exgcd$求出x的最小正整数解即可。
代码
1 | |
POJ 2115 C Looooops
和上一个题差不多，注意直接使用$1«k$会造成溢出。
代码
1 | |
HDU 2161 Primes
注意n小于等于零时结束输入
代码
1 | |
UVA 11827 Maximum GCD
数论题单的题考输入，就挺离谱的
代码
1 | |
SGU 106 The equation
扩欧求一组解后，根据其解集的形式，解出来两个$k$的范围，取个交集就可以了
代码
1 | |
POJ 2478 Farey Sequence
欧拉函数
代码
1 | |
UVA 11752 The Super Powers
这个处理精度好恶心。。
代码
1 | |
UVA 10200 Prime Time
计算结果加上1e-8可以避免0.50000被计算成0.499999的问题
代码
1 | |
UVA 11916 Emoogle Grid
当一个格子在第一行或者上方不能染色时，该格子染色方案为$k$，否则为$k-1$。可以分别统计这两种格子的数目$num1,num2$,则答案为$r=k^{num1}*(k-1)^{num2}$
先令$m$为不能染色的格子行数的最大值$max$（也就是行数可能的最小值），计算一次结果，如果和$r$不一样，再假设行数为$max+1$，如果计算出来的答案$ans2$还和$r$不一样，之后每增加一行，就相当于多$n$个格子染$k-1$个颜色，有式子$r=ans2*((k-1)^{n})^{x}$，用$BSGS$算法求出来x，答案即为$max+x+1$
这题我一个人wa了一整页，好丢人。。。
代码
1 | |
POJ 2116 Death to Binary?
将一个整数转化为$canonical\ Fibonacci\ representation$其实就是从大到小遍历斐波那契数，如果当前数字大于这个斐波那契数就减去它并且这一位表示为1否则表示为0。这道题一个数字最多就四十一位，所以从第四十一个斐波那契数开始遍历就行了。写两个函数，一个把斐波那契形式数字(字符串)转化为一个整数，一个把一个整数转化为斐波那契形式的字符串，之后的操作就很简单了
比较坑的是这个题$fib[0]=1,fib[1]=2$。还有当数字是0的时候，转化成字符串时要注意一下。
代码
1 | |
UVA 11754 Code Feat
要计算出结果有两种做法，一个是dfs枚举所有余数组合再用中国剩余定理求解，另一种是选定一个除数x，对于他对应的余数r，枚举$kx+r$并筛选出符合条件的解
这两种方法交上去亲测都会TLE，第一种方法适用于余数较少的情况，第二种方法适用于余数较多的情况，所以可以根据余数的数量来选择不同的方式求解
代码
1 | |
LightOJ 1356 Prime Independence
如果两个数满足$a=b\ast prime$则a与b素因子的个数必定为一奇一偶，所以可以按照每个数素因子个数的奇偶性建立二分图，存在$a=b\ast prime$关系的两个数之间连边，用$HK$算法求出最大独立集即可。
代码
1 | |