首页 > 代码库 > spoj 7001
spoj 7001
1 /*** 2 大意:计算gcd(x,y,z) =1 0<= x, y , z <= n 问有多少个这样的对 3 莫比乌斯反演:(反演: 用结果推原因) 4 函数m(m)的定义如下: 5
6 7 莫比乌斯反演: 8 9 * f(x) = sigma{g(d)}其中x % d == 0,则g(x) = sigma{miu(d) * f(x/d)} 10 * f(x) = sigma{g(d)}其中d % x == 0,则g(x) = sigma{miu(d/x) * f(d)} 11 12 莫比乌斯反演中miu(x) = 13 14 * 1 {x中含有偶数个不同的质因子} 15 * -1 {x中含有奇数个不同的质因子} 16 * 0 {其他情况} 17 18 本题: 设f(x) = 约数为x 的所有数集合 g(x) = 最大公约数gcd 为x的集合 19 那么g(x) = siga(mu(d)*f(x/d)) x%d==0 20 或者 g(x) = siga(mu(d/x) *f(d)) d%x==0 21 22 在本题中只包含了x,y,z>1 情况 ,,还应加上退化到3个平面上的情况。。 23 1、 f(x) = n/x*n/x*n/x;----〉 g(x) = mu[i] *(n/x*n/x*n/x) 24 2、 加上退化到三个平面 ----〉 g(x) = mu[i]*(n/x+1)*(n/x+1)*(n/x+1) 25 26 或者分开求: 27 1、 三个坐标轴。。3 28 2、 空间中 n/x* n/x*n/x; 29 3、 三个坐标平面: n/x*n/x +n/x*n/x +n/x*n/x 30 **/ 31 1、 第一种方法 32 #include <iostream> 33 #include <cstring> 34 using namespace std; 35 36 const int maxn = 1000050; 37 int pri[maxn]; 38 int prime[maxn]; 39 int mu[maxn]; 40 41 void pri_mu(){ 42 memset(prime,0,sizeof(prime)); 43 int cnt =0; 44 mu[1] =1; 45 for(int i=2;i<maxn;i++){ 46 if(!prime[i]){ 47 mu[i] =-1; 48 pri[cnt++] = i; 49 } 50 for(int j=0;j<cnt;j++){ 51 if(i*pri[j]>maxn) 52 break; 53 prime[i*pri[j]] = 1; 54 if(i%pri[j]==0){ 55 mu[i*pri[j]] =0; 56 break; 57 }else 58 mu[i*pri[j]] = -mu[i]; 59 } 60 } 61 } 62 63 int main() 64 { 65 pri_mu(); 66 int t; 67 cin>>t; 68 long long n; 69 while(t--){ 70 cin>>n; 71 long long ans =0; 72 for(int i=1;i<=n;i++) 73 ans += (long long )mu[i]*((n/i+1)*(n/i+1)*(n/i+1)-1); 74 cout<<ans<<endl; 75 } 76 return 0; 77 } 78 ---------------------------------------------------------------------------------------------------------- 2、 第二种方法 79 #include <iostream> 80 #include <cstring> 81 using namespace std; 82 83 const int maxn = 1000050; 84 int pri[maxn]; 85 int prime[maxn]; 86 int mu[maxn]; 87 88 void pri_mu(){ 89 memset(prime,0,sizeof(prime)); 90 int cnt =0; 91 mu[1] =1; 92 for(int i=2;i<maxn;i++){ 93 if(!prime[i]){ 94 mu[i] =-1; 95 pri[cnt++] = i; 96 } 97 for(int j=0;j<cnt;j++){ 98 if(i*pri[j]>maxn) 99 break; 100 prime[i*pri[j]] = 1; 101 if(i%pri[j]==0){ 102 mu[i*pri[j]] =0; 103 break; 104 }else 105 mu[i*pri[j]] = -mu[i]; 106 } 107 } 108 } 109 110 int main() 111 { 112 pri_mu(); 113 int t; 114 cin>>t; 115 long long n; 116 while(t--){ 117 cin>>n; 118 long long ans =3; 119 for(int i=1;i<=n;i++) 120 ans += (long long )mu[i]*((n/i)*(n/i)*(n/i+3)); 121 cout<<ans<<endl; 122 } 123 return 0; 124 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。