POJ_2480 Longge's problem【积性函数+欧拉函数的理解与应用】

题目：

Longge is good at mathematics and he likes to think about hard mathematical problems which will be solved by some graceful algorithms. Now a problem comes: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N.

"Oh, I know, I know!" Longge shouts! But do you know? Please solve it.

Input

Input contain several test case.
A number N per line.

Output

For each N, output ,∑gcd(i, N) 1<=i <=N, a line

Sample Input

2

6

Sample Output

3

15

题意分析：

做这题前，首先要对两个概念有一定的理解，积性函数和欧拉函数，浅层次的了解是无法推导出最终答案的，只有深入理解。（这完全是屁话- -！）

分析gcd是积性函数,当a,b互质时，易证

$gcd(a\times b,N) = gcd(a,N)\times gcd(b,N)$

这样，我们也可以得出

$f(N) = \sum_{i=1}^{N}gcd(i,N)$

也是积性函数。

然后我们分析N，如果一个数t，它与N的最大公约数2，即gcd(t,N)=2.那么我们可以得出

$gcd(t/2,N/2) = 1$

有没有发现什么，如果没有，回想欧拉函数的性质φ(N/2)的意义是不超过N/2的所有与N/2互素的数的数量。而这些与N/2互素的数字其实就是所有满足上述条件的t/2，再结合题目，那么φ(N/2)就是所有满足gcd(i,N)=2条件的数的数目。再乘以2就是这些数的和。3, 4, 5, ……依此类推。

现在我们往特殊的情况考虑，假设N是素数p。则

$f(p) = \varphi (p)$

那么当N为p^r次方时,N的与i的最大公约数的值可能有1，p，p^2，……，p^r.

$f(p^r) =1\times \varphi(p^r/1)+p\times \varphi(p^r/p)+\cdots +p^{r-1}\times\varphi(p^r/p^r-1)+p^r\times \varphi(p^r/p^r)$

思路有没有变明朗呢？如果没有，那只能原谅我语文确实是体育老师教的。QAQ

直接拿出大招搞事了。

根据上述的公式，然后结合当为奇数次幂时的欧拉函数公式，直接推出

$f(p^r) =r(p^r-p^{r-1})+p^r$

不得不吐槽下自己，自己在写代码时，因为装*，这个式子我又转换了一下，结果一直WA。看来还是要一步一步来啊。

接下来，玩玩拆数字游戏了，根据素数分解，把N分解成素数分解成素数幂相乘，再根据积性函数性质+上述推导的公式，最终结果就是答案了。写的时候注意下控制long long就可以了。

$N=p_1^{r_1}\times p_2^{r_2}\times \cdots \times p_k^{r_k}$

$f(N)=f(p_{1}^{r_1})\times f(p_{2}^{r_2})\times \cdots \times f(p_{k}^{r_k})$

终于over了。

可以用素数打表再写（47ms)，但是估计数据不多，直接试除速度更快(32ms)。

AC代码：

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long LL;

void solve(LL N)

{

    LL ans = 1;

    for(LL i = 2; i*i <= N; i++)

    {

        if(N%i==0)

        {

            LL r = 0;

            LL t = 1;

            do

            {

                N/=i;

                r++;

                t*=i;

            }while(N%i==0);

            ans*=(r + 1) * t - t / i * r;

        }

    }

    if(N>1)

    {

        ans*=2*N-1;

    }

    printf("%I64d\n", ans);

}

int main()

{

    LL N;

    while(scanf("%I64d", &N) != EOF)

    {

        solve(N);

    }

    return 0;

}

巴特西

POJ_2480 Longge's problem【积性函数+欧拉函数的理解与应用】

最新文章

热门文章