PKU 2773 Happy 2006

http://poj.org/problem?id=2773
数字m,kが入力される。
mと互いな素な数字のうち小さいほうからk番目のものを出力しろというような問題。

mより小さい互いな素な数字を全部求めて、大きい奴はそれを使って出す。

ll m,k;
ll po[1000000];
int sz;

void solve(){
  sz=0;
  for(ll i=1;i<=m;++i)
    if(__gcd(i,m)==1)
      po[sz++]=i;
  cout<<(k-1)/sz*m+po[(k-1)%sz]<<endl;
}

main(){
  while(cin>>m>>k)solve();
}