UVALive2116 The Mobius Function【筛选法+莫比乌斯函数】
The Mobius function M(n) is defined on positive integers as follows: Regionals 2000 >> North America - North Central NA 问题链接:UVALive2116 The Mobius Function AC的C++语言程序如下: /* UVALive2116 The Mobius Function */ #include <bits/stdc++.h> using namespace std; const int N = 10000 / 2; const int SQRTN = sqrt((double) N); bool prime[N + 1]; int primek[N / 7]; // Eratosthenes筛选法 void esieve(void) { memset(prime,true,sizeof(prime)); prime[0] = prime[1] = false; for(int i = 2; i <= SQRTN; i++) { if(prime[i]) { for(int j = i * i; j <= N; j += i) //筛选 prime[j] = false; } } for(int i = 0,j = 0; i <= N; i++) if(prime[i]) primek[j++] = i; } int mobius(int n) { int p = 0; if(n == 1) return 1; for(int i = 0; n >= primek[i] * primek[i]; i++) { if(n % primek[i]) continue; n /= primek[i]; p++; if(n % primek[i]) continue; return 0; } if(n != 1) p++; return (p % 2) ? -1 : 1; } int main() { esieve(); int n,flag = 0; while(~scanf("%d",&n) && n != -1) { if(flag) printf("n"); flag = 1; printf("M(%d) = %dn",n,mobius(n)); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |