Artifact daa89aa8f6eb3e5c0aa30d56173dc0c713fccef3:
0000: 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d .//-------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0040: 0a 2f 2f 20 4d 65 62 69 75 73 20 46 75 6e 63 74 .// Mebius Funct
0050: 69 6f 6e 0a 2f 2f 20 20 20 4f 28 20 73 71 72 74 ion.// O( sqrt
0060: 28 4e 29 20 29 0a 2f 2f 0a 2f 2f 20 6d 65 62 69 (N) ).//.// mebi
0070: 75 73 28 6e 29 20 3d 20 30 20 20 20 20 20 20 69 us(n) = 0 i
0080: 66 20 6e 3d 30 20 6d 6f 64 20 70 2a 70 20 66 6f f n=0 mod p*p fo
0090: 72 20 73 6f 6d 65 20 70 0a 2f 2f 20 6d 65 62 69 r some p.// mebi
00a0: 75 73 28 6e 29 20 3d 20 28 2d 31 29 5e 6b 20 6f us(n) = (-1)^k o
00b0: 74 68 65 72 77 69 73 65 2c 20 77 68 65 72 65 20 therwise, where
00c0: 6b 20 69 73 20 74 68 65 20 6e 75 6d 62 65 72 20 k is the number
00d0: 6f 66 20 6e 27 73 20 70 72 69 6d 65 20 66 61 63 of n's prime fac
00e0: 74 6f 72 73 0a 2f 2f 0a 2f 2f 20 70 72 6f 70 65 tors.//.// prope
00f0: 72 74 69 65 73 3a 0a 2f 2f 20 20 31 3a 20 6d 65 rties:.// 1: me
0100: 62 69 75 73 28 6e 6d 29 20 3d 20 6d 65 62 69 75 bius(nm) = mebiu
0110: 73 28 6e 29 20 6d 65 62 69 75 73 28 6d 29 20 20 s(n) mebius(m)
0120: 20 69 66 20 67 63 64 28 6e 2c 6d 29 3d 31 0a 2f if gcd(n,m)=1./
0130: 2f 20 20 32 3a 20 66 28 6e 29 20 3d 20 53 69 67 / 2: f(n) = Sig
0140: 6d 61 5f 7b 64 7c 6e 7d 20 67 28 64 29 0a 2f 2f ma_{d|n} g(d).//
0150: 20 20 20 20 20 20 20 3c 3d 3e 0a 2f 2f 20 20 20 <=>.//
0160: 20 20 67 28 6e 29 20 3d 20 53 69 67 6d 61 5f 7b g(n) = Sigma_{
0170: 64 7c 6e 7d 20 66 28 64 29 6d 65 62 69 75 73 28 d|n} f(d)mebius(
0180: 6e 2f 64 29 0a 2f 2f 0a 2f 2f 20 56 65 72 69 66 n/d).//.// Verif
0190: 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 43 6f ied by.// - Co
01a0: 64 65 43 72 61 66 74 20 27 31 31 20 50 53 54 52 deCraft '11 PSTR
01b0: 0a 2f 2f 0a 2f 2f 20 46 75 72 74 68 65 72 20 6d .//.// Further m
01c0: 65 6d 6f 69 7a 61 74 69 6f 6e 20 6f 72 20 6d 6f emoization or mo
01d0: 72 65 20 6d 69 67 68 74 20 62 65 20 6e 65 65 64 re might be need
01e0: 65 64 2e 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ed..//----------
01f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0200: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0210: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0220: 2d 2d 2d 0a 0a 69 6e 74 20 6d 65 62 69 75 73 28 ---..int mebius(
0230: 69 6e 74 20 6e 29 0a 7b 0a 09 69 6e 74 20 66 20 int n).{..int f
0240: 3d 20 31 3b 0a 09 66 6f 72 28 69 6e 74 20 71 3d = 1;..for(int q=
0250: 32 3b 20 71 2a 71 3c 3d 6e 3b 20 2b 2b 71 29 0a 2; q*q<=n; ++q).
0260: 09 09 69 66 28 20 6e 25 71 20 3d 3d 20 30 20 29 ..if( n%q == 0 )
0270: 0a 09 09 7b 0a 09 09 09 69 66 28 20 6e 25 28 71 ...{....if( n%(q
0280: 2a 71 29 20 3d 3d 20 30 20 29 0a 09 09 09 09 72 *q) == 0 ).....r
0290: 65 74 75 72 6e 20 30 3b 0a 09 09 09 6e 20 2f 3d eturn 0;....n /=
02a0: 20 71 3b 0a 09 09 09 66 20 2a 3d 20 2d 31 3b 0a q;....f *= -1;.
02b0: 09 09 7d 0a 09 69 66 28 6e 3e 31 29 0a 09 09 66 ..}..if(n>1)...f
02c0: 20 2a 3d 20 2d 31 3b 0a 09 72 65 74 75 72 6e 20 *= -1;..return
02d0: 66 3b 0a 7d 0a 0a f;.}..