欧拉函数和最大公约数的组合应用
生活随笔
收集整理的這篇文章主要介紹了
欧拉函数和最大公约数的组合应用
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
? ? ? ? ? 這種問題一般都是給出限制條件：給你一個數N（N一般很大）,使得在1~N之間能夠找到X使得X滿足gcd（ X , ?N ?） >= M，然后求解相關的問題。
? ? ? ? ?分析：這是一種統計類型的問題。比較容易想到的解法就是枚舉gcd(X,N)的值，對于枚舉到的某個 gcd(X,N) 的值 d，如果令 N = p * d，X = q * d，那么如果 gcd(X,N) = d，一定有 p，q 互質，又有 X <= N，則 q <= p，而這樣的 q 的個數正好對應p的歐拉函數，即滿足gcd(X,N) = d 的X的個數為N/d 的歐拉函數值。應用1：求滿足條件的X的個數。http://acm.hdu.edu.cn/showproblem.php?pid=2588
GCD
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)Problem Description The greatest common divisor GCD(a,b) of two positive integers a and b,sometimes written (a,b),is the largest divisor common to a and b,For example,(1,2)=1,(12,18)=6.
(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M, how many integer X satisfies 1<=X<=N and (X,N)>=M.
Input The first line of input is an integer T(T<=100) representing the number of test cases. The following T lines each contains two numbers N and M (2<=N<=1000000000, 1<=M<=N), representing a test case.
Output For each test case,output the answer on a single line.
Sample Input 3 1 1 10 2 10000 72
Sample Output 1 6 260 分析：對于這個問題，因為只需要求出滿足題意的X的個數，所以可以枚舉最大公約數d，而滿足gcd(X,N) = d 的X的個數就是N/d的歐拉函數，把這些d對應的N/d的歐拉函數值求和即可。 #include<stdio.h> #include<math.h>int euler(int n) {int m = (int)sqrt(n+0.5);int ans = n;for(int i = 2; i <= m; i++)if(n % i == 0){ans = ans / i * (i - 1);while(n % i == 0)n /= i;}if(n > 1)ans = ans / n * (n-1);return ans;}int main() {int t, n, m;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);int ans = 0;for(int i = 1; i * i <= n; i++) //枚舉最大公因數{if(n % i == 0){if(i >= m)ans += euler(n/i);if(i * i != n && n / i >= m)ans += euler(i);}}printf("%d\n", ans);}return 0; }
應用2：求滿足條件的gcd（X,N）的和。http://acm.nyist.net/JudgeOnline/problem.php?pid=998
Sum
時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描述? ? ? ? ? ??給你一個數N,使得在1~N之間能夠找到x使得x滿足gcd（ x , ?N ?） >= M，
求解gcd(x,N)的和
輸入每行輸出兩個數N，M（N,M不超int）
分析：這個題要求gcd(X,N)的和，因為上一題已經求出了滿足題意的個數，所以只需要在上一題的基礎上乘以最大公約數就是最終答案。
#include<stdio.h> #include<math.h> typedef long long LL;LL euler(LL n) //n的歐拉函數值 {LL ans = n;for(LL i = 2; i * i <= n; i++)if(n % i == 0){ans = ans / i * (i - 1);while(n % i == 0)n /= i;}if(n > 1)ans = ans / n * (n-1);return ans;}int main() {LL n, m;while(~scanf("%lld%lld",&n,&m)){LL ans = 0;LL tmp = (LL)sqrt(n+0.5);for(LL i = 1; i <= tmp; i++) //枚舉最大公因數{if(n % i == 0){if(i >= m)ans += euler(n/i) * i;if(i * i != n && n / i >= m)ans += euler(i) * (n / i);}}printf("%lld\n", ans);}return 0; }
應用3：求所有滿足條件的X的和。http://acm.nyist.net/JudgeOnline/problem.php?pid=1007
GCD
時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描述(a,b) can be easily found by the Euclidean algorithm. Now Carp is considering a little more difficult problem:
Given integers N and M,please answer sum of ?X satisfies 1<=X<=N and (X,N)>=M. 輸入
分析：這個題和前兩個題基本上一樣，只需要在枚舉最大公約數d時，求出gcd(X,N) = d 的所有X的和即可。根據上面可以得出：滿足條件的X個數有euler（N/d）個，所以只需要求出不超過N/d且與N/d互素的那些數的和，然后乘以d就是最大公約數為d時對應的部分結果。而不超過N/d且與N/d互素的那些數的和 = N/d * euler(N/d) / 2,注意當N/d = 1時，結果是1而不是0。了解了這些，就可以解決這個題了。
除了1、2以外，所有數的歐拉函數都是偶數。
如果k <= n 并且 (k,n) = 1, 那么(n-k, n) = 1;?
#include<stdio.h> #define mod 1000000007 typedef long long LL;LL euler(LL n) //n的歐拉函數值 {LL ans = n;for(LL i = 2; i * i <= n; i++)if(n % i == 0){ans = ans / i * (i - 1);while(n % i == 0)n /= i;}if(n > 1)ans = ans / n * (n-1);return ans;}LL euler_sum(LL n) //求和n互素的數的和 {if(n == 1) return 1;return n * euler(n) / 2; }int main() {int t;LL n, m;scanf("%d",&t);while(t--){scanf("%lld%lld",&n,&m);LL ans = 0;for(LL i = 1; i * i <= n; i++) //枚舉最大公因數{if(n % i == 0){if(i >= m)ans = (ans + euler_sum(n/i) * i) % mod;if(i * i != n && n / i >= m)ans = (ans + euler_sum(i) * (n / i)) % mod;}}printf("%lld\n", ans);}return 0; }
總結
以上是生活随笔為你收集整理的欧拉函数和最大公约数的组合应用的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 判断两条线段是否相交
- 下一篇： 支撑百万级并发，Netty如何实现高性能