解题报告自选题eulerian

1、EX1【题意简述】求所有满足 ab=N 的有序数对(a,b)的最大公约数的和。【算法分析】把问题要求的写成表达式的形式：NN i1 ji1( i, j)考虑枚举了(i,j)之后，原表达式可以化简为：Nk * |(i, j) |k 1( i, j) 1, i * k N, j * k N |假设枚举了其中较大的 i，那么，j 需要满足的条件是(i,j)=k 和 ji，变形一下 i/k与 j/k 互质，ji。用语言表述就是要求比 i/k 小的与 i/k 互质的数的个数。即(i / k) 。再进一步化简表达式：i*k NNk * (i)k 1i1这里，(i) 是函数2，表示与 i 互质的数的个数。有

2、了以上推导，不难设计出一个 N*sqrt(N)*Q 的算法：算法 1：先预处理函数，之后枚举数对中较大的 i 和它们的统计满足条件的j 的个数。值 k， 之后再用函数来时间复杂度:O(N*sqrt(N)*Q)空间复杂度:O(N)12本题是 spoj3871 的函数参见EXs totient function由于 N 的规模并不是很大，因此，考虑通过预处理去掉时间复杂度中的 Q。设 f(n)为要求计算的的和，考虑 f(n+1)与 f(n)的关系:f(n+1)-f(n)=(n+1，1)+(n+1，2)不难发现，这里所有的值都是 n+1 的约数，同时，数对中较大的那个数 n+1 已经确定，因此，它们

3、的差值是可以用 sqrt(n)的时间计算出来的。这样就可以通过预处理的方式计算出所有 n 的。算法 2：先预处理函数，之后采用类似算法 2 的做法求出 f(n+1)-f(n)，由此求出所有的 f(n)。对于所有的询问，直接查表回答。时间复杂度:O(N*sqrt(N)+Q)空间复杂度:O(N)至此，已经设计出了复杂度相当优秀的算法，但是，N*sqrt(N)的时间复杂度还是以通过本题，还需要一个小小的技巧将复杂度降至N*log(N)。来分析一下算法的瓶颈，在枚举(i,j)的时候，进行了很多无用的枚举，因为(i,j)必须是 i 的约数，而要枚举 i 的约数时，必须花费 sqrt(i)的时间来枚举，其

4、中又有很多不是 i的约数，但是也被枚举了。有没办法，让每次枚举出来的数都是 i 的约数呢?可以先枚举(i,j)，再枚举 i，因为 i 必须是(i,j)这里就有一个实现的小技巧，的倍数，所以每一个枚举出来的 i 都是满足条件的，这样就减少了冗余的枚举。来计算一下时间复杂度：O(N/1+N/2+N/3+N/N)=O(N *log(N)算法 3：先预处理函数，之后采用类似筛选法的方法来实现算法 3，求出 f(n-1)-f(n)。时间复杂度:O(N*log(N)+Q)空间复杂度:O(N)LCM SUM3【题意简述】给出N，计算 LCM(1,n) + LCM(2,n) + . + LCM(n,n)的和，

5、LCM(i,n)表示 i 和n 的最小公倍数。【算法分析】尝试把 lcm 也化归到函数上，做一个简单的变形：lcm(x,N)=x*N/(x,N)枚举意，(x,N)之后，那么，问题就是要求与 N/(x,N)互质的所有 x/(x,N)的和。注函数求的是与某个数互质的数的个数，那么，怎么求和呢？这里，有一个简单而往往被大家忽视的性质：性质 1：对于任何一个数N，如果 i 与 N 互质，那么 N-i 也与 N 互质。证明：假设(N,i)=1,(N,N-i)=k(k1)k|N，k|N-ik|i与假设，假设不成立。有了这一性质，问题就彻底转化成了求函数。根据性质 1，可以把所有与N 互质的数两两分组，每一组的和为 N，因此，设与 N互质的数的和为 f(N),则 f(N)=phi(N)*N/2。至此，结合上一题的想法，可以得到了解决本题的算法：算法 1：先预处理出函数，然后再求出所有的 f(N)，再根据以上