Svtter's Blog

谢天谢地终于过了。

就是求分解质因数后的和，如果是质数那么返回1+n本身。

1. 一开始直接暴力求两个质因数的情况，铁定不对啊。。
2. 第二次发现策略有问题，转为使用枚举质因数，然后发现仅仅是质因数LCM有问题啊。。
3. 第三次没有考虑质数
4. 第四次没有考虑Case
5. 第五次不记得了。
6. 第七次AC，哭了真是。。一定要先分析好题目啊。

今天刷题数论题目的时候有所感想。

1. 首先建立一支比较强悍的ACM队伍第一点就是保证刷题量，看再多的书，不做练习肯定是不行的。
2. 选一本正确的指导教材，比如说李汝佳的白皮书，简单易懂，快捷粗暴，按照给出的分类进行训练，效果更佳。
3. 正确的分类。ACM/ICPC的题目各个方向等等都有，各个都很精通对于大学才刚开始培养的acmer恐怕不是很现实，不如巩固共同部分，着重培养较为偏门的部分。最简单的方法也是通过分类，给学生一个兴趣方向，数论的可以顺带研究密码学等学科，对于以后的长远发展也是有很大的好处 — 反而，样样精通可能造成的结果就是样样不精通。当然，如果敏而好学，那么不局限于这一点。

想想去年这个时间在刷一份简单的模板，感觉用处实在是不大，问题都没有好好的理解。

從維基百科的勾股數條目參考來的通解：

給一個任意數對(X,Y)，用以下公式代替

$A = X^2 – Y^2$

$B = 2XY$

$C = X^2 + Y^2$

得出的A,B,C就是一組勾股數。

若 (X,Y) 恰好互質而且一奇一偶，那麼會得到一組(A,B,C)互質的勾股數。

知道通解後，雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。

按照台湾同胞的题解。 — 勾股数公式也是很神奇的啊。。。

此外还学习了bitset，因为是按位存储，所以比一般的bool来的更加迅速，也更加节省时间。

水题一发。。直接使用floor和ceil函数，然后暴力即可。。。

如果使用快速的方法，就是扩展gcd。其中d的初始值没有关系，最后返回的是gcd(a,b).

暴力算法

扩展gcd算法

速度更快，0.012

题意是由10进制转换成-2进制，但是明显我分析错了，所以写了调了接近一下午的bug。。。

有时间再写正常的题解。

题解：

如果当前数位和输入n符号相同，那么不做处理，如果不同且为1，那么下一位（即左边一位）做+1处理 — 因为下一位是上一位的2倍，就相当于做一个变号处理。

昨天卡了这道题目，今天特意来看看莫比乌斯反演。

其中，$∑_{d|n}$含义为整除.

ACdreamer大大的讲解

看了这篇文章即可= =

wikipedia的公式:

以上就是具体的公式，此外，还有线性筛法:

这段代码也是摘自AC大大。我们得到这个东西有什么用？

简单来说，就是简化计算数论函数和的计算的过程，进行加速。

在HDU5212中，给出的题解是：

这道题需要一些莫比乌斯反演、线性筛的知识

定义$f(x)=x∗(x−1)$

题目所求即为$\Sigma(f(gcd(ai,aj)|i!=j,1≤i,j≤n)$

先用线性筛求出miu在[1,10000]的函数值

利用莫比乌斯反演公式我们可以$O(vlogv)$暴力求解出函数g（就是$f(n)/miu$）在[1,10000]的函数值，其中g满足：

$\Sigma(g(d)|x)$

这样所求答案即为：

$\Sigma(g(d)∗cnt(d)∗cnt(d)|1≤d≤10000)$，其中cnt函数满足：

cnt(x)=在a1,a2,..,an中是x的倍数的个数

而cnt的取值也可以$O(vlogv)$暴力计算出

所以总的时间复杂度就是$O(vlogv)$的

就是这样。

水题一发。无奈自己没有好好审清题意，另外快速幂居然写错了- =

快速幂在过程中修改a的值，但是我却计算成了在偶数时相乘，调试半天。看来还是咩有好好理解啊。

这道题目其实就是推个公式，主要还是考验编程技巧。。

首先double的精度范围是15-16位，浮点数运算还是最快的，依据最后一个答案（总共10组），平方为16位刚好够用。

如果想要最精确的结果，当然还是使用long double或者long long来来保证精度问题。不过计算速度就会有所损失，采取二分的方法加速比较好。

利用double的代码：

利用long long的代码:

不过有一点就是无论怎么个快法，不使用打表肯定是会超时的，所以算出来直接上交即可。= =。这在大赛中应该也是允许的吧。

单例模式确保某个类只有一个实例，而且自行实例化，并向整个系统提供者个实例，提供一个访问它的全局访问点。

核心是：创造私有的构造函数

例如：只有一个实例的东西。

Singleton.java

Client