首页 > 代码库 > hdu--2588--欧拉函数||容斥原理
hdu--2588--欧拉函数||容斥原理
这题 其实我觉得并不是那么容易想到欧拉函数的 但又很容易让你去联想他 因为题目的条件有点感觉适合
擦 这句话 好矛盾啊...
有一点 很重要 这题 很容易因为背景是gcd的 让你去想 一定要用到gcd函数=-=
一开始 我走上了歧途 还好 看了下 数据太大了..10E啊
我们都知道 phi( x )求出的是1-X中与X互质的元素的个数
假设 n>=x且n%x==0 那么就说明gcd(n,x)=x
那么 如果x>=m的话 我们是否就可以得出 ans += phi(n/x)呢？
因为 与n/x互质的元素 再*x 那么它和n的gcd就是x了
这边 一定是互质的 不然的话gcd(n,y*x)就是>x了
不知道 你会不会想 为什么不直接ans += n/x呢？算什么欧拉函数啊..
一旦这样计算的话 会有很多元素被进行重复计算
而我们利用上面的方法 就可以巧妙地使每个满足条件的元素仅仅被计算一次 因为某个元素被++的条件是gcd(n,k*x)==x 这是等式成立 而不是>=的条件下
即使这样做了 我们还是可能会tle 要注意在for遍历的时候是 i<=n/i 这样可以减少遍历很多很多
其实 总而言之 就是找出n的所有大于m的约数 进行ans += phi(n/m)的计算
我这边 写了2个- 一个是开数组的 一个是不开的
至于 数组大小 可以大概估计下
我去计算了下 10^9 = (2*5)^9
根据一个数可以表示成 x = a1^p1 * a2 ^p2 …………an^pn 且a1 a2 .....an都是质数
那么它的约数个数就是(p1+1) * (p2+1) * ......*(pn+1) 因为对于每个ai的指数pi我们都有pi+1个取法 0 , 1 , 2 .....pi我们将它进行组合 就得到了刚刚的式子
所以这边我们可以得到10^9的约数的个数是100 那么我就扩大了100倍的数组 去存 事实证明 也够了 没有出现RE 或者是数据问题？
1 #include <iostream> 2 using namespace std; 3 4 const int size = 10010; 5 int fact[size]; 6 void init( int n , int& cnt ) 7 { 8 for( int i = 1 ; i<=n/i ; i++ ) 9 {10 if( n%i == 0 )11 {12 if(i*i==n)13 fact[cnt++] = i;14 else15 {16 fact[cnt++] = i;17 fact[cnt++] = n/i;18 }19 }20 }21 }22 23 int euler( int n )24 {25 int ans = n;26 for( int i = 2 ; i<=n/i ; i++ )27 {28 if( n%i==0 )29 {30 ans = ans / i * (i-1);31 while( n%i==0 )32 n /= i;33 }34 }35 if(n>1)36 ans = ans / n * (n-1);37 return ans;38 }39 40 int main()41 {42 cin.sync_with_stdio(false);43 int t , n , m , cnt , ans;44 cin >> t;45 while( t-- )46 {47 cin >> n >> m;48 cnt = ans = 0;49 init( n , cnt );50 for( int i = 0 ; i<cnt ; i++ )51 {52 if( fact[i]>=m )53 {54 ans += euler( n/fact[i] );55 }56 }57 cout << ans << endl;58 }59 return 0;60 }
这边 同时要注意下 i * i == n这个特殊例子的判断 也一不注意就会重复计算 当然你也可以选择再-去一次phi(i)就可以了
1 #include <iostream> 2 #include <cmath> 3 using namespace std; 4 5 int euler( int n ) 6 { 7 int ans = n; 8 for( int i = 2 ; i<=n/i ; i++ ) 9 {10 if( n%i==0 )11 {12 ans = ans / i * (i-1);13 while( n%i==0 )14 n /= i;15 }16 }17 if(n>1)18 ans = ans / n * (n-1);19 return ans;20 }21 22 int main()23 {24 cin.sync_with_stdio(false);25 int t , n , m , ans , num;26 double temp , val;27 cin >> t;28 while( t-- )29 {30 cin >> n >> m;31 ans = 0;32 for( int i = 1 ; i<=n/i ; i++ )33 {34 if( n%i ==0 )35 {36 if(i>=m)37 ans += euler(n/i);38 if(n/i>=m)39 ans += euler(i);40 }41 }42 temp = sqrt(n*1.0);43 val = temp - floor(temp);44 if( val==0 )45 {46 num = (int)temp;47 if( num>=m && num*m<=n )48 ans -= euler(num);49 }50 cout << ans << endl;51 }52 return 0;53 }
对于 容斥的解法 肯定是可以的 我先再去想想 -.-
today:
好烦那....
心里的想法太多了...
不能逃避....
可能明白为什么寂寞/孤独其实都是无助 恐慌的一种表现
hdu--2588--欧拉函数||容斥原理