NYOJ 762 第k个互质数（二分 + 容斥）
生活随笔
收集整理的這篇文章主要介紹了
NYOJ 762 第k个互质数（二分 + 容斥）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
第k個互質數
時間限制：1000?ms ?|? 內存限制：65535?KB 難度：4 描述輸入
首先，根據歐幾里得可知，gcd(b * t + a, b) = gcd(a, b)(t為任意整數），則如果a與b互質，則b * t + a與b也一定互質，如果a與b不互質，則b*t+a與b也一定不互質，所以與m互質的數對m取模具有周期性。可以先求出1~m之間有多少個數與m互質，然后根據周期性去求第k個與m互質的數。
#include <cstdio>const int N = 1000005; int a[N];int gcd(int a, int b) {while(b) {int r = a % b;a = b;b = r;}return a; }int main() {int m, k;while(~scanf("%d%d", &m, &k)) {if(m == 1) {printf("%d\n", k);continue;}int num = 0;for(int i = 1; i < m; i++)if(gcd(m, i) == 1)a[num++] = i;int p = k / num;if(k % num == 0) p--;k %= num;if(k == 0) k = num;printf("%d\n", p * m + a[k-1]);}return 0; }用上面的方法可以在POJ上AC，可惜的是，在NYOJ上TLE了。所以要尋找一個更快的解決方案，也就是下面的二分+容斥。
首先對m進行質因數分解，求出m有哪些質因數，然后用容斥求[1, mid]內與m互質的數有多少個。
判斷的時候，[1,mid]之間與m互質的數的數量 = mid - （包含一個質因子的數的個數）+ （包含2個質因子的書的個數）-（包含3個質因子的數的個數）+ （包含4個質因數的數的個數）……
#include <cstdio> // 對n進行素因子分解， fac[0]記錄因子個數； int fac[20]; void Div(int n) {int k = 0;for(int i = 2; i * i <= n; ++i){if(n % i == 0) fac[++k] = i;while(n % i == 0) n /= i;}if(n > 1) fac[++k] = n;fac[0] = k; } // 計算[1, n]內與m互質的數的個數 int que[1<<10]; int Count(int n, int m) {int g = 0, sum = n;que[++g] = 1;for(int i = 1; i <= fac[0]; ++i){int t = g;for(int j = 1; j <= g; ++j){que[++t] = que[j] * fac[i] * -1;sum += n / que[t];}g = t;}return sum; } // 二分，二分枚舉一個答案mid，計算[1, mid]內有多少個數與m互質，讓答案與K比較； int Binary_search(int m, int K){int l = 1, r = 2000000000, mid;while(l <= r){mid = (l + r) >> 1;if(Count(mid, m) >= K) r = mid - 1;else l = mid + 1;}return l; } int main() {int m, K;while(scanf("%d%d", &m, &K) != EOF){Div(m);int ans = Binary_search(m, K);printf("%d\n", ans);}return 0; }
總結
以上是生活随笔為你收集整理的NYOJ 762 第k个互质数（二分 + 容斥）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 你看，公司状告员工不加班，居然还告赢了
- 下一篇： 太赞了：《Spring Framewor