大家好，我是讯享网，很高兴认识大家。



1.题意

给出一行数，求对应的数的欧拉函数值大于给出的数的数的最小和。

2.思路

我们知道素数表的欧拉函数值递增。 设素数a,b，b是a的下一个素数，则phi[a]<ph[b]，且a-b间的所有数的欧拉函数都小于等于phi[a]。 欧拉函数值大于x的数的最小的数就是大于x的最小的素数

3.代码

2.Prime Independence

1.题意

2.思路

3.代码

3.Aladdin and the Flying Carpet

1.题意

给出整数 a 和 b ，求区间[b, a] 内的 a 的约数对的个数，即：满足c*d == a 且 c>=b，d>=b。a 的约数对（比如[2, 5] 与 [5, 2] 为同一对）。

2.思路

线性筛+唯一分解定理 根据唯一分解定理，先将a唯一分解，则a的所有正约数的个数为num = (1 + a1) * (1 + a2) *…(1 + ai)，这里的ai是素因子的指数，见唯一分解定理，因为题目说了不会存在c==d的情况，因此num要除2，去掉重复情况，然后枚举小于b的a的约数，拿num减掉就可以了。

3.代码

4.Sigma Function

1.题意

求从1-n的数中约数和是偶数的数的个数

2.思路

我们还可以发现： 当x为偶数时2x和x^2会有重复的部分 当x为奇数时2x和2x^2会有重复的部分 最后发现x^2和 2x^2涵盖了所有情况，且不重复，因此减去这两中情况的数目即可

3.代码

5.Leading and Trailing

1.题意

求n^k前三位和后三位

2.思路

1.暴力跑肯定超时

2.后三位好求，n^k%1000即可

前三位需要变形：参考大佬的推导

讯享网

接下来我们求k+lgn即可

怎么求呢，有个函数学习一下modf()

求出小数部分b后，计算一下就好啦，不过要注意最后要输出3位，需要控制一下输出格式，当n^k=时，对1000取余结果为0，需要再补2个0

3.代码

6.Goldbach`s Conjecture

1.题意

求n=a+b且a，b都是素数这样的a，b的对数

2.思路

素数筛模板题 遍历素数表prime[i]，若n-prime[i]也是素数，ans++ prime[i]>n/2时结束，因为后面再跑就重复了嘛

3.代码

7.Harmonic Number (II)

1.题意

求n(1+¹⁄₂+¹⁄₃+…+1/n)

2.思路

分块数论

3.代码

8.Pairs Forming LCM

1.题意

在a,b中(a,b<=n),有多少组(a,b) (a<b)满足lcm(a,b)==n;

2.思路

素因子分解：n = p1 ^ e1 * p2 ^ e2 *…*pn ^ en 取n的两个因子a,b a=p1 ^ a1 * p2 ^ a2 *…*pn ^ an b=p1 ^ b1 * p2 ^ b2 *…*pn ^ bn

gcd(a,b)=p1 ^ min(a1,b1) * p2 ^ min(a2,b2) *…*pn ^ min(an,bn) lcm(a,b)=p1 ^ max(a1,b1) * p2 ^ max(a2,b2) …pn ^ max(an,bn)

分解n，n = p1 ^ e1 * p2 ^ e2 *…*pk ^ ek，

lcm(a,b)=p1 ^ max(a1,b1) * p2 ^ max(a2,b2) *…*pk ^ max(ak,bk)

所以，当lcm(a,b)==n时，max(a1,b1)==e1,max(a2,b2)==e2,…max(ak,bk)==ek

当ai == ei时，bi可取 [0, ei] 中的所有数 有 ei+1 种情况，bi==ei时同理。

那么就有2(ei+1)种取法,但是当ai = bi = ei 时有重复，所以取法数为2(ei+1)-1=2ei+1。 除了 (n, n) 所有的情况都出现了两次 那么满足a<=b的有 (2ei + 1)) / 2 + 1 个，+1的情况是a = b的时候参考dl

3.代码

９.Harmonic Number

1.题意

输入ｎ，求调和级数

2.思路

结论题。 当ｎ很小的时候，前缀和预处理，Ｏ(１)访问 当ｎ很大的时候，调和级数的近似和为：f(n)=ln(n)+C+1/(2*n); C为欧拉常数 C = 0.1209

3.代码

10.Mysterious Bacteria

1.题意

x=b^p 给出x求出最小的p

2.思路

开始想两层循环暴力跑，底数从1~2^16（65536），幂从1到32，后来发现不对，大于1e7的样例就跑不出来了。

后来又想用唯一分解定理写，以为要求最大的pi，发现还是不对 补充知识：任何一个数都可以分解成如下形式：x = p1x1*p2x2*p3x3*…*psxs，pi为质数

比如：24 = 2^3 * 3^1 但这里答案并不是3，因为题目要求最后的底数就一个b，所以需要能合并。再如：324 = 3^4 * 2^2，发现p应该是gcd(4, 2) = 2,即324 = 18^2因此得出p=gcd(x1,x2,x3,x4…,xk)

还有一个坑点就是n可以是负数，此时需要转化为正数来求。

如果p是偶数，需要做修正，因为-16 != -2^4，所以，需要除2使其变成奇数，比如-324 = -(18^2) = -324^1 如果p是奇数，一个数的奇数次幂可以是负数，则不需要调整。参考网友

3.代码

错误代码

AC代码

11.Large Division

1.题意

大数取余

2.思路

大数除法模板题

3.代码

Python直接写

12.Fantasy of a Summation

1.题意

优化题目中的代码，题目中复杂度为n^k

2.思路

找规律，写几组样例即可发现一共有kn^k个数，而且每个数出现的次数是一样的，那么每个数出现的次数就是kn ^(k-1),那么答案：ans =∑(i从1到n) a[i] * k * n ^(k-1) = sum * k * n ^(k-1); 用快速幂求即可。

3.代码

13.Help Hanzo

1.题意

求a到b的素数的个数

2.思路

二次筛法

这里的区间范围给定的最大值是2^31 - 1,而用线性筛法求的是[1,n]中的所有质数，因此直接用线性筛法求肯定会直接gg，因此需要通过挖掘某些性质，才能有技巧性的完成。

参考来源

注意点： 1.筛[a,b]之间的素数时，要从第一个大于a并且是素数倍数的数开始，当a，b比较小的时候，可能[a,b]中包含素数p，因此：max((a+p-1)/p * p, 2*p) 2.需要注意偏移量，因为b-a<=1e5,那么s标记数st开到1e5就可以（我们这里开到1e6是因为要筛出2^16以内的素数），如果不做偏移量修正，那么可能需要访问到st[1e9]，显然数组开不到这么大。

3.代码

14.Trailing Zeroes (III)

1.题意

输入q，代表N！末尾有q个0，求出最小的N

2.思路

打表到20!发现： 0-4：末尾无0 5-9：末尾1个0 10-14：末尾2个0 15-19：末尾3个0 … 猜测N每+5，末尾就多1个0 但是这样显然求不到q = 1e8时的N

重新思考： N！末尾的0一定是由2*5产生的。 而且2因子的个数一定比5因子的个数多。 所以只需要求N!的5因子的个数。 用到了一个数论知识： 若p是质数，p<=n，则n!是p的倍数，设p^x是p在n!内的最高幂，则 x=[n/p]+[n/p^2]+ [n/p^3]+…; 而且[n/(ab)]=[[n/a]/b]参考来源

3.代码

15.GCD - Extreme (II)

1.题意

找出一个数的阶乘的末尾0个数是q

2.思路

3.代码

16.Code Feat

1.题意

2.思路

3.代码

17.Emoogle Grid

1.题意

2.思路

3.代码

18.青蛙的约会

1.题意

青蛙A，B在一条环形线上，抽象成数轴，长度为l，起始坐标分别为x、y，单位跳跃距离分别为n，m，问最少走几次l能相遇，若不能相遇输出impossible

2.思路

参考来源

3.代码

19.C Looooops

1.题意

求a+bx≡c(mod 2^k)

2.思路

题目的意思就是 a+bx≡c(mod 2^k) 典型的线性同余方程 转化为 bx-y2^k=c-a 当gcd(b,2^k)能整除c-a的时候 就存在解 通解好求 跑一边exgcd可以得出x0 然后 基础解 x=(c-a)/gcd(b,2^k)x0; 通解为 x0+zz(2^ k/gcd(2^k,b); 显然当zz=0的时候最小 关键是要求出最小正整数解。 对于ax+by=gcd(a,b) 这个方程 我们有通解 x=x0+b/gcd(a,b); 那么怎么求x的最小正整数解。呢 首先知道一点 b/gcd(a,b)是解的最小区间 这个怎么理解呢 假设c为x的解的最小间距，此时d为y的解的间距，所以x=x0+ct，y=y0-d*t（x0，y0为一组特解，t为任意整数）

所以，若最后所求解要求x为最小整数，那么x=(x0%（b/gcd(a,b))+b/gcd(a,b))%(b/gcd(a,b))即为x的最小整数解。

x0%（b/gcd(a,b))使解落到区间-b/gcd(a,b) ~ b/gcd(a,b)，再加上b/gcd(a,b)使解在区间0~2*b/gcd(a,b)，

再模上b/gcd(a,b)，则得到最小整数解参考链接

3.代码

20.Death to Binary?

1.题意

2.思路

3.代码

21.Primes

1.题意

1-16000，是素数输出yes，否则no

2.思路

素数筛筛一遍1-16000 注意1，2要输出no，n<=则结束输出

3.代码

22.Maximum GCD

1.题意

n个数中选2个，求gcd，找出最大的gcd

2.思路

暴力跑 输入很花哨，用getline

3.代码

23.Prime Time

1.题意

对于fn = n^2+ n + 41,n属于[l,r]，求素数的概率

2.思路

跑一下就可 这题结果要加1e-8 前缀和打表，否则超时

3.代码

24.The equation

1.题意

线性方程区间求解的个数

2.思路

参考

3.代码

25.Farey Sequence

1.题意

欧拉函数模板题

2.思路

素数筛+欧拉函数+前缀和

3.代码

26.The Super Powers

1.题意

输出所有可以表示成ａ^b 或者(ａ^ b)^c的数 比如： 16 = 2^4＝ 4^2 64 = 8^2 = 2^6

2.思路

最大到２^64-1暴力找肯定超时

可以想到, 如果ａ^b可以拆分, 那么ｂ一定是个合数 如此看来幂的范围是：[4 - 64) 底数范围：[2, 2^16) a的最大次幂:b = loga(2^64-1) = log(2^64-1) / log(i); 求的过程中会有重复的，用set存即可去重

3.代码