[POJ2773]:Happy 2006

同样是欧拉函数的基本应用。

$\phi (N)$表示$[1,N]$中，$gcd(i,N)==1$的数的个数，同理，其也能表示$[K \times N+1,(K+1) \times N]$中$gcd(i,N)==1$的数的个数，所有这样就能把区间固定下来，然后对于固定的区间扫一遍就行了。

//POJ 2773
//by Cydiater
//2016.10.8
#include <iostream>
#include <iomanip>
#include <cstring>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n)        for(ll i=j;i<=n;i++)
#define down(i,j,n)        for(ll i=j;i>=n;i--)
const int MAXN=1e6+5;
const int LIM=1e6;
const int oo=0x3f3f3f3f;
inline ll read(){
    char ch=getchar();ll x=0,f=1;
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll phi[MAXN],cnt=0,prime[MAXN],N,K,leftt,rightt;
bool vis[MAXN];
namespace solution{
    inline ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
    void pret(){
        phi[1]=1;
        memset(vis,0,sizeof(vis));
        up(i,2,LIM){
            if(!vis[i]){prime[++cnt]=i;phi[i]=i-1;}
            up(j,1,cnt){
                if(prime[j]*i>LIM)break;
                vis[prime[j]*i]=1;
                if(i%prime[j]==0){
                    phi[i*prime[j]]=phi[i]*prime[j];
                    break;
                }else phi[i*prime[j]]=phi[i]*phi[prime[j]];
            }
        }
    }
    void slove(){
        ll PHI=phi[N],tol=0;
        leftt=(K-1)/PHI*N+1;rightt=leftt+N-1;
        K-=(K-1)/PHI*PHI;
        up(i,leftt,rightt){
            if(gcd(i,N)==1)tol++;
            if(tol==K){
                printf("%lld\n",i);
                return;
            }
        }
    }
}
int main(){
    //freopen("input.in","r",stdin);
    using namespace solution;
    pret();
    while(scanf("%lld %lld",&N,&K)!=EOF)slove();
    return 0;
}

巴特西

[POJ2773]:Happy 2006

最新文章

热门文章