簡(jiǎn)單題，看懂題意就好，定義了一個(gè)莫比烏斯函數(shù)，讓你求該函數(shù)的值。預(yù)處理的時(shí)候在素?cái)?shù)篩選的時(shí)候忘記給大于m[i]賦值了，錯(cuò)了好幾次。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000005
bool p[N];
int m[N], M[N], prime[N / 10], top;
int factor[32];
void sieve()
{
memset(p, 1, sizeof(p));
p[0] = p[1] = top = 0;
m[1] = 1;
for(int i = 2; i < 1001; i++)
{
if(p[i])
{
m[i] = -1;//就這里，只給1000以?xún)?nèi)的素?cái)?shù)賦值，錯(cuò)了幾次
prime[top++] = i;
for(int j = i * i; j < N; j += i) p[j] = 0;
}
}
for(int i = 4; i < N; i++)
{
if(p[i])
{
m[i] = -1;
continue;
}
int t = i, k = 0, mk = 0;
for(int j = 0; prime[j] < t && j < top; j++)
{
while(t % prime[j] == 0)
{
factor[k++] = prime[j];
t /= prime[j];
}
}
if(t != 1) factor[k++] = t;
for(int j = 1; j < k; j++)
{
// printf("%d: %d\n", i, factor[j - 1]);
// system("pause");
if(factor[j] == factor[j - 1])
{
mk = 1;
break;
}
}
if(mk) continue;
if(k & 1) m[i] = -1;
else m[i] = 1;
}
for(int i = 1; i < N; i++) M[i] = M[i - 1] + m[i];
}
int main()
{
// freopen("out.txt", "w", stdout);
sieve();
int n;
while(scanf("%d", &n), n)
{
printf("%8d%8d%8d\n", n, m[n], M[n]);
}
return 0;
}