題意： 求與n互質(zhì)的第k個(gè)數(shù)

開始看到這題很蒙 試了好幾種做法都T了 后來(lái)才知道

由于GCD（a,b） =? GCD(b, a%b) = GCD(a%b,b)

所以 GCD（a,b） = GCD(a+b , b) = GCD( (a+b) %b, b) = GCD( a+b*t,b)

本題可以把小于n于n互質(zhì)的數(shù)都求出來(lái)? 后面的于n互質(zhì)的是都是前面第一周期（也就是小于n于n互質(zhì)的數(shù)）+ n的倍數(shù)了

所以先求出k是第一周期的多少倍 用倍數(shù)× n再加上 第k對(duì)n取余個(gè)（第一周期的互質(zhì)數(shù)）

注意結(jié)果有可能爆int

注意取余結(jié)果有可能是0 需要返回p-1倍+第一周期最有一個(gè)數(shù)

code：

#include<cstdio> #include<iostream> #include<vector> #include<cstring> using namespace std; typedef long long ll; const int lim = 1000005; int z[lim]; ll gcd(ll a,ll b){return a%b==0?b:gcd(b,a%b); } int main() {int n,k;while(~scanf("%d%d",&n,&k)){memset(z,0,sizeof(z));z[1]=1;int sze=1;for(int i=2;i<n;i++)if(gcd(i,n)==1)z[++sze]=i;ll p = k/sze;//注意int y = k%sze;if(y==0)p--,y=sze;//注意printf("%lld\n",p*n+z[y]);}return 0; }

這道題還有一個(gè)做法 就是 二分那個(gè)第k個(gè)與n互質(zhì)的數(shù)

利用容斥原理 去做二分查找的判定 那么這個(gè)與n互質(zhì)的個(gè)數(shù)一定是隨上界的上升而增多的

我們計(jì)算與n互質(zhì)的個(gè)數(shù) 可以利用n-與n不互質(zhì)的個(gè)數(shù) = 與n互質(zhì)的個(gè)數(shù)

找出n的所有因子 用 n - ( n/p1 + n/p2 +...n/pn - n/(p1*p2) -n/(p1*p3) -?n/(p1*p4)...+n/(p1*p2*p3）+.....)

即可算出所有與n互質(zhì)的數(shù)的個(gè)數(shù)

?

#include<iostream> #include<cstdio> #include<cctype> #include<limits.h> #include<vector> using namespace std; typedef unsigned long long ll; const ll inf = LONG_MAX; ll n,k; ll sum; vector<int>p;void devide(ll a)// 不必真的去那質(zhì)數(shù)表分解 枚舉分解法 因子也是質(zhì)數(shù) {for(int i=2;i*i<=n;i++){if(a%i==0){p.push_back(i);do a/=i;while(a%i==0);}}if(a>1)p.push_back(a); } void dfs(ll pos,ll now,ll cnt,ll x){//容斥計(jì)算if(pos==p.size()){if(now==1)return;if(cnt&1)sum+=x/now;else sum-=x/now;return;}dfs(pos+1,now*p[pos],cnt+1,x);dfs(pos+1,now,cnt,x); } bool test(ll x) {sum=0;dfs(0,1,0,x);return (x-sum)>=k; } int main() {while(~scanf("%d%d",&n,&k)){p.clear();devide(n);ll mid,l = 1,r = inf;if(k==1){printf("1\n");continue;}ll ans;while(l<r){ mid = (l+r)>>1; if(test(mid))r=mid;else l = mid+1; }printf("%lld\n",r);} return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ-2773 欧几里得 + 二分 + 容斥的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。