http://poj.org/problem?id=2886
#include <functional>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <iterator>
#include <memory.h>
using namespace std;
int tree[500100*4];
int n;
void init( int l, int r, int s ) {
tree[s] = r-l;
if( r > l+1 ) {
int c = (l+r)/2;
init( l, c, s*2 );
init( c, r, s*2+1 );
}
}
void set( int l, int r, int s, int k ) {
int c = (l+r)/2;
tree[s]--;
if( r == l+1 )
return;
else if( k < c )
set( l, c, s*2, k );
else
set( c, r, s*2+1, k );
}
int id;
void find( int l, int r, int s, int count ) {
int c = (l+r)/2;
if( r == l+1 )
id = l;
else if( tree[s*2] >= count )
find( l, c, s*2, count );
else
find( c, r, s*2+1, count-tree[s*2] );
}
int p[500100], s[500100];
void clac_point( ) {
int i, j, h, c;
memset( p, 0, sizeof(p) );
c = 1;
for( i=2; c<500000; i++ ) {
if( !p[i] ) {
c++;
for( j=i+i; j<=500000; j+=i )
if( !p[j] )
p[j] = i, c++;
}
}
s[1] = 1;
for( i=2; i<=500010; i++ ) {
if( !p[i] )
s[i] = 2;
else {
h = i;
for( j=0; h%p[i]==0; h/=p[i], j++ )
;
s[i] = s[ h ]*(j+1);
}
}
}
char name[500010][12];
int num[500010];
int k;
bool input() {
int i;
if( scanf( "%d%d", &n, &k ) != 2 )
return false;
for( i=0; i<n; i++ )
scanf( "%s%d", name[i], num+i );
return true;
}
int main( ) {
int i, m, best, k, j;
clac_point( );
while( input() ) {
best = 1;
for( i=2; i<=n; i++ )
if( s[ best ] < s[ i ] )
best = i;
init( 0, n, 1 );
k = ::k-1;
j = ::k;
m = n;
for( i=1; i<best; i++ ) {
set( 0, n, 1, k );
m--;
if( num[k] > 0 )
j = (j-1+num[k]-1)%m+1;
else {
j = (j+num[k]-1)%m;
if( j < 0 ) j+=m;
j++;
}
find( 0, n, 1, j );
k = id;
// printf( "%s %dn", name[k], j );
}
printf( "%s %dn", name[k], s[best] );
}
return 0;
}