1
0

Square_Roots.dpr 2.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
  1. program doshide;
  2. const
  3. maxn = 100000;
  4. var
  5. m : array [ 0..maxn, 1..2 ] of longint;
  6. p, value, times, ans : array [ 0..maxn ] of longint;
  7. n : longint;
  8. procedure Swap( var a, b : longint );
  9. var
  10. tmp : longint;
  11. begin
  12. tmp := a;
  13. a := b;
  14. b := tmp;
  15. end;
  16. procedure Qsort( s, t : longint );
  17. var
  18. i, j, x : longint;
  19. begin
  20. i := s;
  21. j := t;
  22. x := p[ ( s + t ) shr 1 ];
  23. repeat
  24. while ( m[ p[ i ] ][ 2 ] < m[ x ][ 2 ] ) do
  25. inc( i );
  26. while ( m[ p[ j ] ][ 2 ] > m[ x ][ 2 ] ) do
  27. dec( j );
  28. if ( i <= j ) then
  29. begin
  30. Swap( p[ i ], p[ j ] );
  31. inc( i );
  32. dec( j );
  33. end;
  34. until ( i > j );
  35. if ( s < j ) then
  36. Qsort( s, j );
  37. if ( i < t ) then
  38. Qsort( i, t );
  39. end;
  40. procedure ReadData;
  41. var
  42. i : longint;
  43. begin
  44. read( n );
  45. for i := 1 to n do
  46. begin
  47. read( m[ i ][ 1 ], m[ i ][ 2 ] );
  48. p[ i ] := i;
  49. end;
  50. Qsort( 1, n );
  51. end;
  52. procedure Work;
  53. var
  54. i, id : longint;
  55. procedure GetValue( x : longint );
  56. var
  57. i : longint;
  58. begin
  59. inc( id );
  60. for i := 0 to x shr 1 do
  61. begin
  62. times[ i * i mod x ] := id;
  63. value[ i * i mod x ] := i;
  64. end;
  65. end;
  66. begin
  67. id := 0;
  68. for i := 1 to n do
  69. begin
  70. if ( m[ p[ i ] ][ 2 ] <> m[ p[ i - 1 ] ][ 2 ] ) then
  71. GetValue( m[ p[ i ] ][ 2 ] );
  72. if ( times[ m[ p[ i ] ][ 1 ] ] <> id ) then
  73. ans[ p[ i ] ] := - 1
  74. else
  75. ans[ p[ i ] ] := value[ m[ p[ i ] ][ 1 ] ];
  76. end;
  77. for i := 1 to n do
  78. if ( ans[ i ] = - 1 ) then
  79. writeln( 'No root' )
  80. else
  81. writeln( ans[ i ], ' ', m[ i ][ 2 ] - ans[ i ] );
  82. end;
  83. begin
  84. assign( input, 'ural1132.in' );
  85. reset( input );
  86. assign( output, 'ural1132.out' );
  87. rewrite( output );
  88. ReadData;
  89. Work;
  90. close( input );
  91. close( output );
  92. end.