memset(xh,0,sizeof(xh));
for(i=1;i<=x&&pri[i]*pri[i]<=n;i++)
{
if(n%pri[i]==0)
{
sum=sum*(pri[i]-1)/pri[i];
for(j=1;j*pri[i]<=q;j++)
xh[pri[i]*j]=1;//这个地方和上面的可能越界，所以要用__int64
}
while(n%pri[i]==0)
{
n/=pri[i];
}
}
if(n>1)
{
sum=sum*(n-1)/n;
for(j=1;j*n<=q;j++)
xh[j*n]=1;
}
//sum m以内与m互素的个数
LL t=k%sum,p=k/sum;
if(t==0)
{
t=sum;
p--;
}
LL temp=0;
for(i=1;i<=q;i++)
{
if(xh[i]==0)
temp++;
if(temp==t)
{
printf("%I64d\n",p*q+i);
break;
}
}
}
return 0;
}
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef __int64 LL;
const int N=1000002;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
inline int in()
{
char ch = getchar();
int data = 0;
while (ch < '0' || ch > '9')
{
ch = getchar();
}
do
{
data=data*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return data;
}
int xh[N];
LL pri[N],x;
bool vis[N];
void prime()//求素数
{
LL i,j;
x=0;
memset(vis,false,sizeof(vis));
for(i=2;i
if(!vis[i])
pri[++x]=i;
for(j=1;j<=x&&pri[j]*i
vis[pri[j]*i]=true;
if(i%pri[j]==0)
break;
}
}
}
int main()
{
LL n,k,i,j;
prime();
while(scanf("%I64d%I64d",&n,&k)!=EOF)
{
LL q=n,sum=n;
if(n==1)
{
printf("%I64d\n",k);
continue;
}
memset(xh,0,sizeof(xh));
for(i=1;i<=x&&pri[i]*pri[i]<=n;i++)
{
if(n%pri[i]==0)
{
sum=sum*(pri[i]-1)/pri[i];
for(j=1;j*pri[i]<=q;j++)
xh[pri[i]*j]=1;//这个地方和上面的可能越界，所以要用__int64
}
while(n%pri[i]==0)
{
n/=pri[i];
}
}
if(n>1)
{
sum=sum*(n-1)/n;
for(j=1;j*n<=q;j++)
xh[j*n]=1;
}
//sum m以内与m互素的个数
LL t=k%sum,p=k/sum;
if(t==0)
{
t=sum;
p--;
}
LL temp=0;
for(i=1;i<=q;i++)
{
if(xh[i]==0)
temp++;
if(temp==t)
{
printf("%I64d\n",p*q+i);
break;
}
}
}
return 0;
}