[数论]HDU_2879

传送门

首先给出,He函数是一个积性函数,然后He[p^n]=2,其中p是素数.那么He[n]就是2^k,k是不同素数的个数.那么HeHe[n]函数就是计算所有的n/p,p是素数.那么这题就变成了证明He[n]是素数函数.下面给出一个简单证明,如有错误还请指出:

首先He[p]=2.p是素数. x^2=x(mod p)—->p|x(x-1).因为x<p所以p不整除x也不整除x-1.所以成立的情况下是x=1或者x=0.

He[p^k]=2,证明类似上面的

对于不同的两个素数p和q,He[pq]=4=He[p]He[q];

首先x=0和x=1是肯定成立的,

现在由x^2=x(mod p*q)

   --->p*q|x(x-1)

 假设x=k*p[k<q]

 ------>p*q|k*p(k*p-1)

------->q|k(k*p-1)

——->q|(k*p-1) 因为k<q q是素数 所以gcd(k,q)=1

——->kp+tq=1

这里就变成了这个方程的解,由扩展欧几里得知,这个方程有解,但是k在[0,q-1]之内的解就一个,所以这里多一个解,同理设x=kp又有一个解,所以x^2=x(mod pq)有4个解(x=0 ,x=1 ,x=kp, x=kq)

—->He[pq]=4=He[p]He[q];

那么He[p1^r1p2^r2……*pk^rk]=2^k然后可以进一步算出HeHe只需要算n以内每个素数的倍数的个数.