jzd同學今天告訴了我們一道關于歐拉函數的題，一開始覺得毫無頭緒，當身旁的erge同學切完開始裝（xiao）逼（zhang）的時候，他無意間透露的歐拉函數四個字啟發了我，最近做了一道很相似的題HDU1695 這道題就是讓你求x 屬于[a,b], y 屬于[c,d] 求gcd(x,y)==k 的x,y的個數，這道題顯然是一道容斥原理的裸題，我們把x和y都同時div一個k，然后就是容斥加歐拉函數啦。

題面

給定兩個正整數n和m，問有多少個x滿足1≤x≤n 且 gcd(n,x)≥m。題目有多組數據。

一句話題意非常的舒服，看完題應該第一個想法就是容斥，然而當時和jzd討論的時候他說有問題讓我再想想，我想了半天也沒想出來哪里有問題，于是我便丟在那沒管了，回家的路上和thkkk一起討論了下發現容斥貌似是可以的，復雜度也是對的，回家想了想細節打了一下，細節有點多，然后跑得比歐拉函數的還要快。

先講講容斥的做法，我們考慮n的每一個約數d，如果d是>=m的那么d在[1,n]中所有的倍數都是可行的，那么答案加上n/d，但是會存在d被重復計算的問題，我們果斷搬上容斥原理，我所記得的容斥原理貌似就是奇加偶減（蒟蒻只知道這個）然后我想到的便是用一個二進制枚舉每個因子的選擇情況，每次乘起來，得到一個lcm,如果使用的因子個數為奇數那么貢獻為正，否則為負，貢獻為n/lcm。不多說了，在紙上模擬下就知道了。

/*************************************************************************> File Name: GGG2.cpp> Author: Drinkwater-cnyali> Created Time: 2017/8/25 23:58:07 ************************************************************************/#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm>using namespace std;#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i) #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i) #define mem(a, b) memset((a), b, sizeof(a))typedef long long LL;LL read() {LL sum = 0, fg = 1; char c = getchar();while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }return sum * fg; }const int maxn = 100000; LL T,n,m; LL cnt,a[maxn],b[maxn],num;void Div() {for(int i = 1; i * i <= n; ++i){if(n % i)continue;if(i * i != n)if(n/i>=m)a[++cnt] = n/i;if(i>=m)a[++cnt] = i;} }LL gcd(LL a,LL b) {return b == 0 ? a : gcd(b , a % b); }int main() {T = read();while(T--){n = read(),m = read();cnt = 0;Div();num = 0;sort(a+1,a+1+cnt);REP(i,1,cnt){int flag = 0;REP(j,1,i-1)if(a[i]%a[j]==0){flag = 1;break;}if(!flag)b[++num] = a[i];}LL ans = 0;REP(i,1,(1<<num)-1){int cc = __builtin_popcount(i);LL mlt = 1;REP(j,1,num)if(i & 1<<(j-1)){mlt = mlt / gcd(mlt,b[j]) * b[j];if(mlt > n)break;}if(cc&1)ans += n/mlt;else ans -= n/mlt;}cout<<ans<<endl;}return 0; }

接下來是歐拉函數的做法，歐拉函數的本質是φ(n)為小于n與n互質的個數，gcd(n,x)==1 知道這個就很好想了，我們考慮每一個大于等于m的因子，我們令gcd(n,x)==d n,x同時除d那么就是n/d的φ值，是不是很巧妙？

/*************************************************************************> File Name: GGG.cpp> Author: Drinkwater-cnyali> Created Time: 2017/8/25 23:24:26 ************************************************************************/#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm>using namespace std;#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i) #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i) #define mem(a, b) memset((a), b, sizeof(a))typedef long long LL; LL read() {LL sum = 0, fg = 1; char c = getchar();while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); }while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }return sum * fg; }LL get_phi(LL x) {LL res = x;for(int i = 2; i * i <= x; ++i){if(x % i == 0){res = res / i * (i - 1);while(x % i== 0)x /= i;}}if(x > 1)res = res/ x * (x - 1);return res; }LL T,n,m;int main() {T = read();while(T--){n = read(),m = read();LL ans = 0;for(int i = 1; i * i <= n; ++i){if(n % i)continue;if(n/i >= m && i * i != n)ans += get_phi(i);if(i >= m) ans += get_phi(n/i);}cout<<ans<<endl;}return 0; }

轉載于:https://www.cnblogs.com/brodrinkwater/p/7527981.html

總結

以上是生活随笔為你收集整理的欧拉函数的一道练习题（附加容斥做法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。